Blog Logo
Research Scientist @ Foundation AI
·
read
Image Source: https://analyticsindiamag.com/wp-content/uploads/2017/01/algoritms.png
· · ·

Merge Sort

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Time Complexity: \(O(n\,log\,n)\)

Pseudocode

Merge(A, p, q, r):
  n1 = p - q + 1
  n2 = r - q
  L = arr[n1]
  R = arr[n2]
  for k = 1 to n1:
    L[k] = A[p + k - 1]
  for k = 1 to n2:
    R[k] = A[q + k]
  i = 1
  j = 1
  for k = p to r:
    if L[i] <= R[j]:
      A[k] = L[i]
      i++
    else 
      A[k] = R[j]
      j++

Java Code


public class MergeSort {
    
    public static int[] merge(int[] arr_l, int[] arr_r) {
        
        int[] arr = new int[arr_l.length + arr_r.length];
        int k;
        int l = 0;
        int r = 0;
        for(k = 0; k < arr.length; k++) {
            if(arr_l[l] <= arr_r[r]) {
                arr[k] = arr_l[l];
                l++;
            } else {
                arr[k] = arr_r[r];
                r++;
            }
            if(l==arr_l.length || r==arr_r.length) {
                k++;
                break;
            }
        }
        
        for(int j = l; j < arr_l.length; j++) {
            arr[k] = arr_l[j];
            k++;
        }
        for(int j = r; j < arr_r.length; j++) {
            arr[k] = arr_r[j];
            k++;
        }
        
        return arr;
        
    }
    
    public static int[] merge_sort(int[] arr) {
        
        if(arr.length == 1) return arr;
        
        int mid = (int) arr.length/2;
        
        int left = mid;
        int[] arr_l = new int[left];
        for(int k = 0; k < left; k++) arr_l[k] = arr[k];
        
        int right = arr.length-mid;
        int[] arr_r = new int[right];
        for(int k = 0; k < right; k++) arr_r[k] = arr[mid+k];
        
        arr_l = merge_sort(arr_l);
        arr_r = merge_sort(arr_r);
        arr = merge(arr_l, arr_r);
        
        return arr;
        
    }
    
    public static void print_arr(int[] arr) {
        
        for(int i: arr) {
            System.out.printf("%d ", i);
        }
        System.out.println("\n");
        
    }

    public static void main(String[] args) {

        int[] arr = {1, 9, 8, 7, 6, 10, 5, 9};
        MergeSort.print_arr(MergeSort.merge_sort(arr));

    }

}

Java Code for Inplace Merge Sort


public class MergeSortInplace {
    
    static int[] arr;
    
    public static void merge(int start, int mid, int end) {
        
        int[] aux_arr = new int[end-start+1];
        int k;
        
        for(k = 0; k < end-start+1; k++) {
            aux_arr[k] = arr[start + k];
        }
        
        k=start;
        int i = 0;
        int j = mid-start+1;
        
        while(i <= mid-start && j <= end-start) {
            if(aux_arr[i] <= aux_arr[j]) {
                arr[k] = aux_arr[i];
                i++;
            } else {
                arr[k] = aux_arr[j];
                j++;
            }
            k++;
        }
        
        while(i<= mid-start) {
            arr[k] = aux_arr[i];
            i++;
            k++;
        }
        
        while(j<=end-start) {
            arr[k] = aux_arr[j];
            j++;
            k++;
        }
        
    }
    
    public static void merge_sort(int start, int end) {
        
        if(start >= end) return;
        int mid = start + (end-start)/2;
        merge_sort(start, mid);
        merge_sort(mid+1, end);
        merge(start, mid, end);
        
    }
    
    public static void print_arr(int[] arr) {
        
        for(int i: arr) System.out.printf("%d ", i);
        System.out.println();
        
    }

    public static void main(String[] args) {
        
        int[] arr = {1, 3, 2, 5, 4, 7, 6, 10, 5, 8, 9};
        MergeSortInplace.arr = arr;
        merge_sort(0, MergeSortInplace.arr.length-1);
        print_arr(MergeSortInplace.arr);

    }

}

REFERENCES:

Introduction to Algorithms 3rd Edition - Chapter 2
Merge Sort - Wikipedia

· · ·