Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sub-lists in a manner that results into a sorted list.

Sorting by merging is a recursive, divide-and-conquer strategy. In the base case, we have a sequence with exactly one element in it. Since such a sequence is already sorted, there is nothing to be done. To sort a sequence of n>1 elements:

1. Divide the sequence into two sequences of length [n/2] and [n/2]

2. Recursively sort each of the two sub sequences; and then

3. Merge the sorted sub sequence to obtain the final result.

Example:

Example:

class MergeSort { int[] a; int[] tmp; MergeSort(int[] arr) { a = arr; tmp = new int[a.length]; } void msort() { sort(0, a.length-1); } void sort(int left, int right) { if(left < right) { int mid =(left+right)/2; sort(left, mid); sort(mid+1, right); merge(left, mid, right); } } void merge(int left, int mid, int right) { int i = left; int j = left; int k = mid+1; while( j<= mid && k <= right ) { if(a[j] < a[k]) tmp[i++] = a[j++]; else tmp[i++] = a[k++]; } while( j <= mid ) tmp[i++] = a[j++]; for(i=left; i < k; i++) a[i] = tmp[i]; } } //////////////////// MergeSortDemo.java /////////////////////// class MergeSortDemo { public static void main(String[] args) { int[] arr ={75, 40, 10, 90, 50, 95, 55, 15, 65}; MergeSort ms = new MergeSort(arr); ms.msort(); System.out.print("Sorted array:"); for( int i=0; i < arr.length; i++) System.out.print(arr[i] + " "); } }

Time complexity of merger sort

## 0 comments:

## Post a Comment

Note: only a member of this blog may post a comment.