Properties of Merge Sort

In the last chapter we looked at how the running time of selection sort, bubble sort, and insertion sort depends on the input, we saw that all three work in place, and we asked which of them are stable. Let’s ask the same questions about merge sort.

Time, space, and input order

Here are the four sorts side by side. Bubble sort here is the version with early termination. Read the best-case and worst-case columns together to see whether a sort is sensitive to the order of the input.

Algorithm	Best case	Worst case	Auxiliary space
Selection sort	$O (n^{2})$	$O (n^{2})$	$O (1)$
Bubble sort	$O (n)$	$O (n^{2})$	$O (1)$
Insertion sort	$O (n)$	$O (n^{2})$	$O (1)$
Merge sort	$O (n lo g n)$	$O (n lo g n)$	$O (n)$

Merge sort is in a different time complexity class. The three earlier sorts are quadratic. Merge sort is linearithmic, the $O (n lo g n)$ class we named when we studied common running times.

Merge sort is not in place. Its merge creates a temporary array of size up to $n$ , which is where the $O (n)$ auxiliary space comes from. The other three sorts are in place.

Merge sort, like selection sort, is not sensitive to the order of the input. Its best case and worst case match. Bubble sort and insertion sort finish an already-sorted array in linear time.

Stability

Look at the comparison in our merge. When the front of the left half (arr[i]) and the front of the right half (arr[j]) are equal, we take from the left:

} else if (arr[i] <= arr[j]) {  // tie -> take from the left (earlier) half
  merged[k] = arr[i++];
} else {
  merged[k] = arr[j++];
}

The left half holds the elements that came earlier in the array, so taking from it first on a tie keeps equal elements in their original order. This makes merge sort stable.

If you change that <= to a <, the algorithm still sorts correctly, but on a tie it takes from the right half first, so it is no longer stable.