Properties of Merge Sort

Exercise

Fill in this table for selection sort, bubble sort with early termination, insertion sort, and merge sort.

Algorithm	Best case	Worst case	Auxiliary space
Selection sort
Bubble sort
Insertion sort
Merge sort

Solution

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)$

Solution

No. In place means $O (1)$ auxiliary space. The merge step allocates a temporary array as large as the range it merges, up to $n$ elements, so merge sort uses $O (n)$ auxiliary space. Writing the result back into arr does not change that.

Exercise

Here is the comparison in a merge where arr[i] is the front of the left half and arr[j] is the front of the right half:

} else if (arr[i] < arr[j]) {
  merged[k] = arr[i++];
} else {
  merged[k] = arr[j++];
}

Is a merge sort built on this merge stable? Explain. If you say it is not, show the change that makes it stable.

Solution

No. On a tie the condition is false, so the merge takes the element from the right half first, ahead of an equal element that came earlier in the array. Changing < to <= makes it stable: a tie then takes from the left half, which holds the earlier elements, so equal elements keep their original order.

Solution

Insertion sort. On a nearly sorted array almost every key stops after one comparison, so it runs close to its $O (n)$ best case. Merge sort does its full $O (n lo g n)$ regardless of the order, and selection sort does its full $O (n^{2})$ . Bubble sort with early termination finishes an already-sorted array in $O (n)$ , but a small element near the end moves left only one slot per pass, so it can still cost $O (n^{2})$ on a nearly sorted array.