Sorting Algorithms
A list is far easier to work with when its items are in order. An ordered list is quicker to scan by eye, quicker to search with a computer, and some fast search methods will only work at all once the data has been arranged from smallest to largest. Putting items into order — ascending numbers, or names into alphabetical order — is the job of a sorting method.
A sorting algorithm takes an unordered list and rearranges it into the required order. There is no single ‘best’ sorting algorithm; each one trades speed, memory use and simplicity against the others. This lesson looks at three of them — bubble sort, insertion sort and merge sort — and at how to judge which is the better choice for a job.
Bubble sort
Bubble sort works by comparing pairs of neighbouring items and swapping them when they are in the wrong order. A swap simply exchanges the two values. Starting from the front, the algorithm compares the first and second items, then the second and third, and so on to the end of the list.
Each complete run through the list is called a pass. During the first pass the largest value keeps being swapped rightwards until it reaches the end — it ‘bubbles’ to the top. Bubble sort keeps making passes, each one settling the next-largest value into place, until it completes a whole pass without making a single swap. When that happens the list is known to be in order.
Bubble sort only ever compares adjacent items. After each full pass, the largest remaining value is guaranteed to be in its correct place at the end of the list.
Sort the list 5, 1, 4, 2 into ascending order. Pass 1: compare 5 and 1, they are in the wrong order so swap → 1, 5, 4, 2. Compare 5 and 4, swap → 1, 4, 5, 2. Compare 5 and 2, swap → 1, 4, 2, 5. The largest value, 5, has now bubbled to the end. Pass 2: compare 1 and 4, no swap; compare 4 and 2, swap → 1, 2, 4, 5. A final pass makes no swaps at all, so the algorithm stops — the list is sorted.
Insertion sort
Insertion sort builds a sorted section at the start of the list, one item at a time. The very first item is treated as a sorted list of one. The algorithm then takes the next unsorted item and inserts it into its correct position within the already-sorted section, shifting any larger items one place to the right to make room.
This is much like sorting a hand of playing cards: you pick up each new card and slide it into the right spot among the cards you already hold. Because insertion sort moves items by shifting them along rather than repeatedly swapping across the whole list, it is often very quick when a list is already nearly in order — each new item usually needs to move only a short distance.
Sort the list 3, 7, 4, 1. The sorted section starts as just [3]. Take 7: it is larger than 3, so it stays where it is → [3, 7]. Take 4: it is smaller than 7, so shift 7 right; it is larger than 3, so insert 4 between them → [3, 4, 7]. Take 1: it is smaller than every sorted item, so shift 7, 4 and 3 each one place right and place 1 at the front → [1, 3, 4, 7]. The list is now sorted.
Merge sort
Merge sort uses a strategy called divide and conquer. It repeatedly splits the list in half, and splits the halves again, until every sub-list holds just a single item. A list of one item cannot be out of order, so each of these tiny lists is already sorted.
The clever part is the merging. Two sorted sub-lists are combined by repeatedly comparing their front items and taking the smaller one, until all the values have been copied into a single, larger sorted list. This merging is repeated, joining pairs of sub-lists into ever-longer sorted lists, until one fully sorted list remains.
Merge sort first splits the list down to single items, then merges pairs back together in order. A sub-list of one item is treated as already sorted because a single value cannot be out of order.
Sort the list 6, 2, 7, 1. Split it into [6, 2] and [7, 1], then split again into [6], [2], [7] and [1]. Now merge: [6] and [2] combine to [2, 6]; [7] and [1] combine to [1, 7]. Finally merge [2, 6] with [1, 7]: compare 2 and 1, take 1; compare 2 and 7, take 2; compare 6 and 7, take 6; then take the last value, 7. The result is [1, 2, 6, 7].
Comparing the algorithms
Bubble sort and insertion sort are simple to understand and easy to write. They also work in place, meaning they need very little extra memory. Their weakness is speed: as a list grows, the number of comparisons they must make rises steeply, so they become slow on large amounts of data.
Merge sort copes far better with large lists — the amount of work it does grows much more gently as the list gets longer. The trade-off is that it needs extra memory to hold all the sub-lists while they are being merged, and it is more complicated to write than the other two.
As a rule of thumb, the simple sorts are perfectly good for short lists, while merge sort is usually the better choice for large ones. Of the three, bubble sort generally does the most comparing and swapping, so in practice it tends to be the slowest.
Merge sort is much faster than bubble sort on large lists, but it uses more memory because it must store the sub-lists while merging them.