Sorting Algorithms Compared with Examples

Sorting algorithms are among the first algorithms every programmer studies, and they are still used everywhere: in databases, search engines, spreadsheets, compilers and graphics. Sorted data makes searching, merging and finding duplicates much faster. Comparing the main algorithms also teaches the core ideas of algorithm analysis: time complexity, space use, stability and the effect of the input order.

How sorting algorithms are compared

Four properties matter most:

• Time complexity: how the number of steps grows with the number of items n, in the best, average and worst case. It is written in Big O notation.
• Space complexity: extra memory needed. An in place sort needs only a constant amount of extra memory (or a small stack).
• Stability: whether equal keys keep their original relative order.
• Adaptivity: whether the algorithm runs faster on input that is already partly sorted.

A further distinction is between comparison sorts, which only compare pairs of keys, and non comparison sorts, which use the digits or values of the keys directly.

Simple quadratic sorting algorithms

Bubble sort repeatedly steps through the list and swaps adjacent items that are out of order. Large items “bubble” to the end. With an early exit when a pass makes no swaps, it takes linear time on sorted input, but it is slow in general and is used mainly for teaching.

Selection sort finds the smallest remaining item and swaps it into the next position. It always makes n(n − 1)/2 comparisons but at most n − 1 swaps, which can matter when writes are expensive. It is not stable in its usual array form.

Insertion sort takes each item and inserts it into the correct place among the already sorted items to its left, like sorting playing cards in your hand. It is stable, in place and adaptive: on nearly sorted data it runs in close to linear time. That is why fast library sorts use it for small sub arrays.

Efficient n log n sorting algorithms

Merge sort is a divide and conquer method. It splits the array into halves, sorts each half recursively and merges the two sorted halves in linear time. Its running time follows the recurrence below and is n log n in every case. It is stable but needs an extra array of size n for merging. It is the natural choice for sorting linked lists and for external sorting of files too large for memory.

$$T(n) = 2\,T\!\left(\frac{n}{2}\right) + \Theta(n) \;\Rightarrow\; T(n) = \Theta(n \log n)$$

Download diagram (WebP)

Quicksort picks a pivot, partitions the array so that smaller items go left and larger items go right, and then sorts the two parts recursively. On average it runs in n log n time with small constant factors and sorts in place, so it is often the fastest in practice. A poor pivot on every step, for example always taking the first item of an already sorted array, gives quadratic time. Random pivots or the median of three items make this very unlikely.

Heapsort builds a binary max heap from the array, then repeatedly swaps the largest item to the end and restores the heap. It guarantees n log n time and sorts in place, but it is not stable and its memory access pattern is less cache friendly than quicksort.

Linear time non comparison sorts

Counting sort counts how many times each key value occurs and uses those counts to place items directly. It runs in time proportional to n + k, where k is the range of key values, so it suits small integer ranges. Radix sort sorts numbers or strings digit by digit, using a stable sort such as counting sort for each digit, in time proportional to d(n + k) for d digits. Bucket sort spreads items into buckets by value and is fast when the input is uniformly distributed.

These methods beat the n log n limit because they do not rely on comparisons.

Sorting algorithms comparison table

All entries are orders of growth (Big O).

The n log n lower bound

Any comparison sort can be drawn as a decision tree in which each comparison has two outcomes and each leaf is one possible ordering. There are n! orderings, so the tree height, the worst case number of comparisons, is at least log₂(n!), which grows as n log n. No comparison sort can do better in the worst case, so merge sort and heapsort are asymptotically optimal.

$$C_\text{worst}(n) \ge \lceil \log_2 n! \rceil \approx n \log_2 n$$

Key formulas for sorting algorithms

Which sorting algorithm to use

• Use the language library sort in almost every program. Python’s list.sort and Java’s sort for objects use Timsort, a stable hybrid of merge sort and insertion sort that is very fast on partly sorted data. Java sorts primitive arrays with a dual pivot quicksort.
• Small arrays or nearly sorted data: insertion sort.
• Stability required: merge sort or Timsort.
• Guaranteed worst case with little memory: heapsort.
• Integers or fixed length keys in a known range: counting or radix sort.
• Data larger than memory: external merge sort, as used by database engines.

The choice of data structure also matters: the stack and queue used in recursion and in iterative versions of these algorithms affects memory use.

Sorting algorithms interview and viva questions

1. What is a stable sorting algorithm? Give two examples. A stable sort keeps equal keys in their original relative order. Insertion sort and merge sort are stable.
2. Why is insertion sort fast on nearly sorted data? Each item moves only a short distance to reach its place, so the inner loop stops early and the total work is close to linear.
3. What causes the worst case of quicksort? Pivots that split the array very unevenly at every step, such as always choosing the first item of an already sorted array, give quadratic time.
4. Why can no comparison sort beat n log n in the worst case? A decision tree with n! leaves must have height at least log₂(n!), which grows as n log n.
5. How does counting sort avoid the n log n limit? It does not compare keys; it counts occurrences of each key value and places items directly, which takes time proportional to n + k.