Sorting Algorithms
Comparing Sorting Algorithms
Comparing sorting algorithms means judging each one by its main steps, how easy it is to write, how fast it is on large lists, how fast it is on lists that are almost in order, and whether it needs extra memory.
Main steps
Bubble sort repeatedly compares neighbouring items and swaps any pair that is in the wrong order, making passes until a complete pass makes no swaps. Insertion sort treats the left part of the list as sorted and inserts the next item into its correct place, shifting larger items right. Merge sort splits the list into halves until each sub-list has one item, then merges sorted sub-lists in order until one list remains. Merging the lists in order is what sorts the data; merge sort does not merge unsorted lists and sort them afterwards.
Comparing the three sorts
| Feature | Bubble sort | Insertion sort | Merge sort |
|---|---|---|---|
| Main steps | Swaps neighbouring pairs | Inserts one item at a time | Divides, then merges sorted sub-lists |
| Ease of writing | Simple to understand and write | Simple to write | More complex to write |
| Speed on large lists | Slow: many comparisons and swaps | Slower than merge sort | Much quicker than both |
| Speed on nearly sorted lists | Can be quick: stops after a pass with no swaps | Can be quick: few shifts needed | No such shortcut |
| Extra memory | No extra lists | No extra lists | Uses extra memory for temporary lists |
Bubble sort and insertion sort are simpler to write because each uses a small number of loops and comparisons. Insertion sort is quick on short lists, and it also copes well when only a few items are out of place because it needs few shifts. Bubble sort is slow on large lists because it makes many comparisons and swaps. Merge sort handles large lists far faster, but writing it is harder and it requires additional memory for the temporary sub-lists it builds.
These comparisons use the main steps of each algorithm; formal efficiency measures such as best-case and worst-case analysis or Big O notation, and built-in sorting functions, are not part of this comparison.
Practise this
OCR GCSE Computer Science · Sorting Algorithms