Merge Sort

An efficient sorting algorithm which splits the input array in 2 halves, sorts these two halves individually and then merges them to a single sorted array.

Merge Sort is a divide and conquer algorithm. It divides the provided array in two halves, calls itself for the two halves and then merges the two sorted halves. This process is done recursively to sort the whole array.

Merge sort is one of the most efficient algorithms for sorting an array of values.
Characteristic Value Notes
Time Complexity O(nlogn) For all cases, worst/best/average
Space Complexity O(n) Temporary array for extra storage

Advantages:
  1. Efficient sorting in average case, way better than bubble, selection and insertion sort.
  2. Recursive and efficient implementation using simple functions.

Disadvantages:
  1. Takes extra space of O(n) time, therefore, if the size of data being held by an array is large, the function becomes inefficient.
  2. Has best case complexity of O(nlogn) only, while insertion and bubble sort have best case complexity of O(n) (sorting an already sorted array)

Implementation


Merge sort recursively consists of 2 functions, one function for merging the sorted arrays and one for recursively sorting the split arrays.

The logic of the merge() function is pretty simple, it works with 3 iterators and one temporary array to hold the result of the merging:
  1. itr_1: Holds the index to the value to compare in the first sorted array.
  2. itr_2: Holds the index to the value to compare in the second sorted array.
  3. itr_3: Holds the last index of the temporary array.

> It compares the values in both the sorted arrays, and then appends the smaller among the two to the temporary array. It then increments the iterator to the array holding the smaller value by 1.
> If any one array reaches it's end, the other array is copied directly to the temporary array.
> At the end, the temporary array is copied back to the main array for an in-place sorting algorithm.

Code for the following in C++: 
            
// merge function
void merge(int arr[], int start, int end) {
  int mid = (start + end) / 2;

  int i = start;
  int j = mid + 1;
  int k = start;

  int temp[1000];

  while(i <= mid && j <= end) {
    if(arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  while(i <= mid) {
    temp[k++] = arr[i++];
  }

  while(j <= end) {
    temp[k++] = arr[j++];
  }

  // copy temp array to original array
  for(int x = start; x <= end; ++x) {
    arr[x] = temp[x];
  }
}

The second function is the one used for recursively sorting arrays and the sub-arrays.
This function, for every array in input :
> Splits that array in half and recursively sorts the 2 halves.
> Merges the two sorted halves using the previously defined merge() function in a single array.

As this function is a recursive function it has 2 cases:
  1. Base Case : This is the stopping case/bottom case for a recursive function. For an input array, if the size of that array is 0/1 i.e. an empty array or an array with only 1 element is always sorted in itself.
  2. Recursive Case : This is the case the function will make recursive calls on a smaller subproblem. For any array with size > 1, we can split that array in halves, sort these halves recursively, and merge the sorted halves.


Code for the following in C++: 
            
// merge_sort function
void merge_sort(int arr[], int start, int end) {
  // base case
  if(start >= end) {
    return;
  }

  int mid = (start + end) / 2;

  // recursive case -> sort the half arrays
  merge_sort(arr, start, mid);
  merge_sort(arr, mid + 1, end);

  // merge the sorted halves
  merge(arr, start, end);
}