What you'll learn

  1. Quick answer
  2. The Simple O(n squared) Sorts
  3. Merge Sort: Predictable and Stable
  4. Quicksort: Fast Until It Isn't
  5. Stability, and Why It Matters
  6. What to Actually Use
  7. FAQ

Quick Answer

Bubble, selection and insertion sort are all O(n squared) and exist mainly to teach the ideas, though insertion sort is genuinely fast on small or nearly-sorted data. Merge sort is O(n log n) in every case and stable, but needs O(n) extra memory. Quicksort is O(n log n) on average with O(1) extra space, but degrades to O(n squared) on bad pivots. In real code, use your language's built-in sort — it is a tuned hybrid that beats anything you would write by hand.

The Simple O(n squared) Sorts

Three algorithms share the same complexity and very different characters.

Bubble sort repeatedly walks the list swapping adjacent out-of-order pairs, so large values "bubble" to the end. It is the easiest to explain and the least useful. Its one redeeming feature is that with an early-exit flag it detects an already-sorted list in a single O(n) pass.

def bubble_sort(a):
    for i in range(len(a)):
        swapped = False
        for j in range(len(a) - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # already sorted, stop early
            break

Selection sort finds the smallest remaining element and swaps it into place. Its distinguishing property is that it makes at most n swaps — the fewest of any of these. That matters only when writing is far more expensive than reading, which is rare but real for some hardware.

Insertion sort builds a sorted section at the front, taking each new element and sliding it back to its place. This is how most people sort a hand of playing cards. Crucially it is O(n) on nearly-sorted data and has very low overhead, which is why real library sorts switch to it for small chunks.

So of the three, only insertion sort survives into production code — as a component of something larger.

Merge Sort: Predictable and Stable

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves. The merge step is the clever part: since both halves are sorted, you compare only their front elements and take the smaller.

[38, 27, 43, 3, 9, 82, 10]
     split → [38, 27, 43]  [3, 9, 82, 10]
     split → [38] [27, 43]  ...
     merge → [27, 38, 43]  [3, 9, 10, 82]
     merge → [3, 9, 10, 27, 38, 43, 82]

Its complexity is O(n log n) in the best, average and worst case — no input can make it behave badly. The log n comes from halving until you reach single elements; the n comes from each merge level touching every element once.

Two properties make it the right choice in specific situations. It is stable, meaning equal elements keep their original relative order, which matters when sorting records by one field after another. And it works well when data does not fit in memory, because merging streams sequentially rather than jumping around — external sorts of huge files are merge sorts.

The cost is O(n) extra space for the merge buffers. That is the trade against quicksort.

Quicksort: Fast Until It Isn't

Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recurses on both sides. The pivot lands in its final position after each partition.

On average it is O(n log n) and in practice it is usually faster than merge sort, because it partitions in place with excellent cache behaviour and no allocation. It needs only O(log n) space for the recursion stack.

The catch is the pivot. If the pivot is consistently the smallest or largest element, each partition removes just one element instead of halving, and the algorithm degrades to O(n squared). The classic trigger is naive quicksort with a first-element pivot on an already-sorted array — the input that intuition says should be easiest is the one that breaks it.

Real implementations avoid this with median-of-three pivots or randomised pivot selection, which makes the bad case vanishingly unlikely. Quicksort is also not stable in its usual form, because partitioning swaps distant elements.

Stability, and Why It Matters

A sort is stable if elements that compare equal keep their original relative order. This sounds academic until you sort by two things.

Suppose you have students already sorted by name, and you now sort by marks. With a stable sort, students with equal marks remain in name order — you get a sensible two-level ordering for free. With an unstable sort, their order among themselves is arbitrary, and the earlier sort is silently thrown away.

Sorted by name:   Amit(85)  Bina(90)  Chetan(85)  Divya(90)

Stable sort by marks:    Amit(85)  Chetan(85)  Bina(90)  Divya(90)
                         names still in order within each mark

Unstable sort by marks:  Chetan(85)  Amit(85)  Divya(90)  Bina(90)
                         name order lost

Merge sort and insertion sort are stable. Quicksort and heapsort are not. This is why Java uses a merge-sort variant for objects but quicksort for primitives — with primitives there is no hidden extra data, so stability is meaningless.

What to Actually Use

In production: the built-in sort, essentially always. Library sorts are tuned hybrids refined over decades, and a hand-written sort will be slower and buggier.

Python's sorted() and list.sort() use Timsort, which detects already-ordered runs and merges them — genuinely O(n) on sorted or reverse-sorted input, which is common in real data. Java uses Timsort for objects and a dual-pivot quicksort for primitives. C++ std::sort uses introsort, a quicksort that switches to heapsort if recursion gets too deep, guaranteeing O(n log n) while keeping quicksort's speed.

Notice the pattern: every real implementation is a hybrid that switches to insertion sort for small pieces, because the constant factors win below a few dozen elements.

The reason to learn these anyway is that interviews ask you to reason about trade-offs, and the concepts transfer. Divide and conquer from merge sort, partitioning from quicksort, and the stability question all show up well beyond sorting itself.

Frequently Asked Questions

Which sorting algorithm is fastest? For general use, quicksort is usually fastest in practice thanks to in-place partitioning and cache behaviour, though merge sort has better worst-case guarantees. In real code the built-in sort beats both, since it is a tuned hybrid. On nearly-sorted data, Timsort and insertion sort approach O(n).
Why is quicksort O(n squared) in the worst case? If the pivot is always the smallest or largest element, each partition removes only one element rather than halving the array, producing n levels of recursion with n work each. Naive quicksort on an already-sorted array is the classic trigger. Randomised or median-of-three pivots make this vanishingly rare.
What does a stable sort mean? Elements comparing equal keep their original relative order. It matters when sorting by multiple fields in sequence — sorting by marks after sorting by name preserves name order within each mark. Merge sort and insertion sort are stable; quicksort and heapsort are not.
Should I ever write my own sorting algorithm? Almost never in production. Built-ins are faster, well tested and handle edge cases. Write one to learn the ideas, to satisfy an interview, or in the rare case where you have a special constraint — such as counting sort when values fall in a small known range, which beats O(n log n).
What sorting algorithm does Python use? Timsort, a hybrid of merge sort and insertion sort. It finds runs of already-ordered elements and merges them, making it O(n) on sorted or reverse-sorted input and O(n log n) in the worst case. It is also stable.