Merge Sort

The basic idea of the algorithm 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 (Rosetta code). Merge sort follows divide-and-conquer approach.

Worst case performance - O(n log n)

Source - Wikipedia

 C++

 void merge_sort(int array[], int low, int high)  
 {  
   if (low < high)  
   {  
     int middle = (low + high) / 2;  
     merge_sort(array,low, middle);  
     merge_sort(array,middle + 1, high);  
     merge(array, low, middle, high);  
   }  
 }  
   
 void merge(int array[], int low, int middle, int high)  
 {  
   int size1 = middle - low + 1;  
   int size2 = high - middle;  
   int left[size1 + 1];  
   int right[size2 + 1];  
   for (int i = 0; i < size1; i++)  
   {  
     left[i] = array[low + i];  
   }  
   for (int j = 0; j < size2; j++)  
   {  
     right[j] = array[middle + j + 1];  
   }  
   left[size1] = numeric_limits<int>::max();;  
   right[size2] = numeric_limits<int>::max();;  
   int i = 0;  
   int j = 0;  
   for (int k = low; k <= high; k++)  
   {  
     if (left[i] <= right[j])  
     {  
       array[k] = left[i];  
       i++;  
     }  
     else  
     {  
       array[k] = right[j];  
       j++;  
     }  
   }  
 }   

Java

   static int[] array = {5, 4, 8, 3, 1, 2, 9, 6, 7, 10};  
   
   static void merge_sort(int[] array, int low, int high) {  
       if (low < high) {  
         int middle = (low + high) / 2;  
         merge_sort(array, low, middle);  
         merge_sort(array, middle + 1, high);  
         merge(array, low, middle, high);  
       }  
    }  
   
   static void merge(int[] array, int low, int middle, int high) {  
       int size1 = middle - low + 1;  
       int size2 = high - middle;  
       int[] left = new int[size1 + 1];  
       int[] right = new int[size2 + 1];  
       for (int i = 0; i < size1; i++) {  
         left[i] = array[low + i];  
       }  
       for (int j = 0; j < size2; j++) {  
         right[j] = array[middle + j + 1];  
       }  
       left[size1] = Integer.MAX_VALUE;  
       right[size2] = Integer.MAX_VALUE;  
       int i = 0;  
       int j = 0;  
       for (int k = low; k <= high; k++) {  
         if (left[i] <= right[j]) {  
           array[k] = left[i];  
           i++;  
         } else {  
           array[k] = right[j];  
           j++;  
         }  
       }  
    }  

Matlab

   function array = merge_sort(array,low,high)  
     if(low < high)  
       middle = floor((low + high)/2);  
       array = merge_sort(array,low, middle);  
       array = merge_sort(array,middle + 1, high);  
       array = merge(array, low, middle, high);  
     end  
   end  
   
   function array = merge(array,low,middle,high)  
     size1 = middle - low + 1;  
     size2 = high - middle;  
     left = zeros(1,size1+1);  
     right = zeros(1,size2+1);  
     for i=1:size1  
       left(i) = array(low+i-1);  
     end  
     for j=1:size2  
       right(j) = array(middle+j);  
     end  
     left(size1+1) = inf;  
     right(size2+1) = inf;  
     i = 1;  
     j = 1;  
     for k=low:high  
       if left(i)<= right(j)  
         array(k) = left(i);  
         i = i + 1;  
       else  
         array(k) = right(j);  
         j = j + 1;  
       end  
     end  
   end   

Python 

import math

def merge(array,low,middle,high):
    size1 = middle - low + 1
    size2 = high - middle
    left = [0]* (size1+1)
    right = [0]* (size2+1)
    for i in range(size1):
        left[i] = array[low+i]
    for j in range(size2):
        right[j] = array[middle+j+1]
    left[size1] = float("inf")
    right[size2] = float("inf")
    i = 0
    j = 0
    for k in range(low,high+1):
        if left[i]<= right[j]:
            array[k] = left[i]
            i = i + 1
        else:
            array[k] = right[j]
            j = j + 1
   
def merge_sort(array,low,high):
    if low<high:
        middle = int(math.floor((low+high)/2))
        merge_sort(array,low,middle)
        merge_sort(array,middle+1,high)
        merge(array,low,middle,high)