Merge sort

2018-04-23

Content:

1. The idea

Say we want to sort an array in ascending order.

The merge sort algorithm’s idea is that assuming you’re already had the first half and the second half of the array sorted, you can now merge them to create a sorted array (thus the name merge sort).

Figure 1. Merge sort visualization
(Source: Wikipedia - Merge sort)

2. Implementation

N = length of array.

Say we want to sort an array from index 0 to N-1 (a whole array).

1
2
3
4

void merge_sort(vector<int>& arr) {
  int n = arr.size();
  merge_sort(arr, 0, n-1);
}

Like I mentioned: if we are sorting the array from index left to index right, and we have the first half and second half sorted, we can merge them in linear time so that the whole left to right is sorted:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// overload
void merge_sort(vector<int>& arr, int left, int right) {
  int mid = left + (right - left) / 2;

  // Assume that [left, mid] and (mid, right] is sorted,
  // now we merge them
  int* temp = new int[right-left+1];
  int i = left, j = mid+1, k = 0;
  while(i<=mid && j<=right) {
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else temp[k++] = arr[j++];
  }
  while(i <= mid) temp[k++] = arr[i++];
  while(j <= right) temp[k++] = arr[j++];

  // Copy temp back to arr[left, right]
  for(k = left, k <= right; k++)
    arr[k] = temp[k-left];

  delete temp;
}

How do we get the first half and second half sorted? We can do it recursively (divide and conquer) by calling merge_sort for those 2 halves. Our base case is when left >= right, we need to do nothing:

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

void merge_sort(vector<int>& arr, int left, int right) {
  // Base case
  if (left >= right) return;
  
  int mid = left + (right - left) / 2;
  
  merge_sort(arr, left, mid);     // sort first half
  merge_sort(arr, mid+1, right);  // sort second half

  // Now we merge them
  int* temp = new int[right-left+1];
  int i = left, j = mid+1, k = 0;
  while(i<=mid && j<=right) {
    // If tie, take the left one, this makes
    // merge sort stable.
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else temp[k++] = arr[j++];
  }
  while(i <= mid) temp[k++] = arr[i++];
  while(j <= right) temp[k++] = arr[j++];

  // Copy temp back to arr[left, right]
  for(k = left, k <= right; k++)
    arr[k] = temp[k-left];

  delete temp;
}

3. Complexity analysis

Time complexity:

Let’s call $T(N)$ = number of operations when compute merge_sort(arr, left, right) given $right - left = N$.

In each merge_sort function:

  • We sort 1st and 2nd halves, which takes $2T(\frac{N}{2})$.
  • We merge those two halves, which takes $2N$ operations.

So: $T(N) = 2T(N/2) + 2N$, easy to show that this has a time complexity of $O(NlogN)$ (in average and worst case).

Space complexity:

Let’s call $S(N)$ = number of storage units when compute merge_sort(arr, left, right) given $right - left = N$.

In each merge_sort function:

  • We sort 1st and 2nd halves, which takes $max(S(\frac{N}{2})$.
  • We allocate the temp array which takes $N$ storage units.

So: $S(N) = max(S(\frac{N}{2}), N) = N$, so the space complexity is $O(N)$.

If using linked-list, we can merge arrays without temp, the space complexity is $O(logN)$ (the Recursion Depth, or the space of the Call Stack - part of the computer memory, where a recursive algorithm allocates its temporary data).

4. Properties

  • Merge sort is a stable sort algorithm.