Comparing the four sorting algorithms

Overview

Recall questions on the time and space complexity of bubble, insertion, merge and quick sort, which are stable, how each handles sorted and reversed data, and ranking the four sorts for small and very large lists.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Summarise the best, average and worst-case time complexity of bubble, insertion, merge and quick sort.

   Model answer

   Bubble sort: O(n) best when optimised with a swap flag, O(n squared) average and worst. Insertion sort: O(n) best, O(n squared) average and worst. Merge sort: O(n log n) in all three cases. Quick sort: O(n log n) best and average, O(n squared) worst.

2. 2

   Summarise the space requirement of the four sorts.

   Model answer

   Bubble sort and insertion sort are O(1), sorting in place with only a temporary variable. Quick sort is O(log n) on average for its recursion stack, rising to O(n) in the worst case, but it needs no copy of the data. Merge sort is O(n), because merging requires extra storage proportional to the data.

3. 3

   Which of the four are stable, and which are not?

   Model answer

   Insertion sort and merge sort are stable, so items with equal keys keep their original relative order. The standard quick sort is not, because partitioning can swap equal items past one another. Bubble sort is stable if it only swaps items that are strictly out of order.

4. 4

   Which sorts benefit from data that is already nearly in order, and which do not care?

   Model answer

   Insertion sort benefits most, approaching O(n) because each item moves only a short distance. An optimised bubble sort also benefits, finishing in few passes. Merge sort does not care, since its work is fixed by the list length. Quick sort with a first-item pivot is actively harmed, because near-sorted data drives it towards its O(n squared) worst case.

5. 5

   Rank the four sorts for a list of about 20 items and justify the ranking.

   Model answer

   Insertion sort first, then bubble sort, with merge and quick sort last. At that size the quadratic growth costs almost nothing, while the recursive sorts pay for function calls and, in merge sort's case, copying. The complexity ranking that matters for large n is reversed by the constant factors at small n.

6. 6

   Rank the four sorts for a list of a million random items and justify the ranking.

   Model answer

   Quick sort first on speed, with merge sort close behind and preferable if the worst case must be excluded or stability is needed. Insertion sort and bubble sort are unusable: a million squared is of the order of a million million operations against roughly twenty million for the O(n log n) sorts.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.