Merge Sort

The merge sort is a recursive sort of order n*log(n). It is notable for having a worst case and average complexity of O(n*log(n)), and a best case complexity of O(n) (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its "divide and conquer" description.

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]; } }