Worst case performance : O(n log n)
Best case performance : O(n log n)
Average case performance : O(n log n)
Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
This is the pseudocode of merge sort
function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else var middle = length(m) / 2 for each x in m up to middle - 1 add x to left for each x in m at and after middle add x to right left = mergesort(left) right = mergesort(right) if last(left) ≤ first(right) append right to left return left result = merge(left, right) return result function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | import java.util.*; public class Mergesort{ public static void main(String[] args){ int [] a = {22,63,22,54,102,1,38,36,89,98,99,200,36}; mergeSort(a); System.out.println(Arrays.toString(a)); } public static void mergeSort(int []a){ int[] tmp = new int[a.length]; mergeSort(a,tmp,0,a.length - 1); } private static void mergeSort(int []a, int []tmp, int left, int right){ if( left < right ){ int center = (left + right) / 2; mergeSort(a, tmp, left, center); mergeSort(a, tmp, center + 1, right); merge(a, tmp, left, center + 1, right); } } private static void merge(int[]a,int[]tmp,int left,int right,int rightEnd ){ int leftEnd = right - 1; int k = left; int num = rightEnd - left + 1; while(left <= leftEnd && right <= rightEnd){ if(a[left] < a[right]) tmp[k++] = a[left++]; else tmp[k++] = a[right++]; } // Copy rest of first half while(left <= leftEnd) tmp[k++] = a[left++]; // Copy rest of right half while(right <= rightEnd) tmp[k++] = a[right++]; // Copy temp array back for(int i = 0; i < num; i++, rightEnd--) a[rightEnd] = tmp[rightEnd]; } } |
No comments:
Post a Comment