Merge Sort

This page provides introduction to Merge Sort.

Overview

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer strategy to sort a list or array of elements. It breaks down the sorting process into smaller subproblems, sorts them individually, and then merges them back together to create a fully sorted list.

Let's sort array below, with merge sort:

$$[38, 27, 43, 3, 9, 82, 10]$$

Below are the steps performed during the merge sort:

• Split the array into two halves recursively until each subarray contains a single element.
• Sort the subarrays as they are merged back together.
• Merge the sorted subarrays to produce the final sorted array.

Java

public void mergeSort(int[] arr, int lo, int hi) {
  if(from < to) {
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, lo, mid + 1);

    merge(arr, lo, mid, hi);
  }
}


public void merge(int[] arr, int lo, int mid, int hi) {
  int n1 = mid - lo + 1;
  int n2 = hi - mid;

  int[] left = new int[n1];
  for(int i = 0; i < n1; i++) left[i] = arr[lo + i];

  int i = 0, j = 0;
  int index = lo;
  while(i < n1 && j < n2) {
    if(left[i] < arr[j + mid + 1]) {
      arr[index++] = left[i];
      i++;
    }
    else {
      arr[index++] = arr[j + mid + 1];
      j++;
    }
  }

  while(i < n1) {
    arr[index++] =left[i++];
  } 

  while(j < n2) {
    arr[index++] = left[j + mid + 1];
    j++;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

Since there are $\text{O(log N)}$ levels in divide and conquer procees and each level involves $\text{N}$ work for merging, the total time complexity is:

$$\text{O}(\text{N log N})$$

Space Complexity

Additional space is required for temporary array used during the merge phase.

$$\text{O(N)}$$