Sorting algorithms explained, with Big O

Sorting algorithms put a list into order, such as numbers from smallest to largest or names from A to Z. Simple ones, like bubble sort and insertion sort, compare neighbouring items and take O(n²) time, so they slow down badly on big lists. Faster ones, like merge sort and quick sort, split the list up and take O(n log n) time on average.

Watch any of them run in the Algorithm Visualiser. It animates bubble, insertion, selection, merge, quick and heap sort one step at a time, counts the comparisons and swaps, and shows the real code beside each step.

Try it

Algorithm Visualiser

Watch sorting and pathfinding algorithms run step by step

Open the simulatorGo to its page

Bubble sort

Bubble sort walks through the list comparing each pair of neighbours and swapping them if they are in the wrong order. After one pass the biggest item has "bubbled" to the end. Repeat until a pass makes no swaps.

Sorting 6, 2, 9, 4, 1. In the first pass: 6 and 2 swap, 6 and 9 stay, 9 and 4 swap, 9 and 1 swap. That is 4 comparisons and 3 swaps, and 9 is now in place.

It is easy to write and needs no extra memory, but a list of n items can take n − 1 passes of up to n − 1 comparisons each, so it is O(n²). Its one strength: on a list that is already sorted, one pass with no swaps proves it, which is O(n).

Insertion sort

Insertion sort builds a sorted part at the front of the list, one item at a time. Take the next item and slide it left past every bigger item until it reaches its place, the way many people sort a hand of cards. It is also O(n²) in the worst case, but it is fast on small or nearly sorted lists, which is why real-world sorts use it for short runs.

Merge sort

Merge sort uses divide and conquer. Split the list in half, again and again, until every piece holds one item. A single item is already sorted. Then merge the pieces back together in pairs, always taking the smaller front item from the two lists being merged.

Split:  7 3 8 1 5 2 6 4
        7 3 8 1  |  5 2 6 4
        7 3 | 8 1 | 5 2 | 6 4
        7|3|8|1|5|2|6|4

Merge:  3 7 | 1 8 | 2 5 | 4 6
        1 3 7 8  |  2 4 5 6
        1 2 3 4 5 6 7 8

Halving 8 items takes 3 levels, because 2³ = 8, and each level of merging touches every item once. That gives about n × log₂ n steps: O(n log n) in every case. The cost is memory: merging needs a second list to copy into.

Quick sort

Quick sort also divides and conquers, but does the hard work before splitting. Pick one item as the pivot, then move everything smaller to its left and everything bigger to its right. The pivot is now in its final place. Quick sort each side the same way.

On average this is O(n log n) and it is often the fastest in practice, because it sorts in place and works well with how memory is cached. Its weakness is a bad pivot. If the pivot is always the smallest or largest item, for example by picking the first item of a list that is already sorted, every split is lopsided and it falls to O(n²). Choosing the middle item or a random one avoids that.

Sorting algorithms compared

The gap is huge for big lists. For 1,000 items, n² is 1,000,000 while n log₂ n is about 10,000. For a million items, n² is a million million, about 50,000 times more work than n log₂ n.

Matching an algorithm to how its work grows is a key exam skill. Try it, then press Mark to check your answer in the course:

What "stable" means

A stable sort keeps items that compare equal in their original order. Sort a class list by surname, then stably by form group, and each form group stays in surname order. Merge sort and insertion sort are stable; quick sort and heap sort usually are not.

Which sorting algorithm do real languages use?

Mostly hybrids. Python's built-in sort is based on Timsort, which finds runs of items that are already in order, sorts short stretches with insertion sort and joins them with merging. It is stable and very fast on real data, which is often partly sorted already. You rarely need to write a sort yourself, but knowing how they work tells you why sorted() is fast and when a list is worth keeping in order.

Bubble sort in JavaScript

Paste this into the Code Editor to run it:

function bubbleSort(list) {
  const a = [...list];
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;   // a pass with no swaps: sorted
  }
  return a;
}

console.log(bubbleSort([6, 2, 9, 4, 1]));   // [1, 2, 4, 6, 9]

Common mistakes

• Stopping bubble sort after one pass. One pass only fixes the largest item. Keep going until a pass makes no swaps.
• Merging by joining lists end to end. Merging means looking at the first item left in each half and taking whichever is smaller, every time.
• Saying quick sort is always O(n log n). Its worst case is O(n²).
• Thinking Big O gives the exact time. It describes how the work grows as n grows, not the seconds it takes.

Read next

Computer Science · Programming and algorithmsAlgorithm visualizer: sorting and pathfinding step by stepWatch six sorting algorithms and four pathfinding searches run step by step, with comparison and swap counts, big O, and the real code beside them.