Sorting algorithms — complexity

What just happened?

Sorting — arranging data in ascending or descending order — is one of the most common operations in computer science, and performance is decided by the choice of algorithm. We raised the number of elements to 1,000 and compared two strategies: simple bubble sort and clever merge sort.

Computational complexity (big-O notation)

Complexity describes how the number of operations grows with the data size $n$. Simple algorithms (bubble sort, selection sort) compare every element with every other, so they perform on the order of:

Clever algorithms — merge sort (devised by John von Neumann in 1945) or quicksort — thanks to the “divide and conquer” strategy (split the data into halves, sort recursively, merge the sorted parts) achieve:

Why such an enormous difference?

For small n the difference is tiny. But for n = 1000 that is ~1,000,000 operations ($n^2$) versus ~10,000 ($n\log n$) — a hundred times fewer. Sorting a million elements with an $O(n^2)$ algorithm takes trillions of operations (hours, even days), while $O(n\log n)$ — a few tens of millions (a fraction of a second). The choice of algorithm decides whether a program runs for seconds or years.

A foundation of theoretical computer science

Complexity analysis lets us predict whether a program can realistically be run, even before we write it. That is why standard libraries (in Python, Java, C++) use algorithms of order $n\log n$ internally, rather than naive quadratic loops.

Why this matters for your exams:

The topic of complexity itself lies outside the high-school curriculum (it straddles mathematics and computer science), but logarithms and the growth rate of functions certainly are on it. Being able to compare how $n^2$ grows faster than $n\log n$ is the same intuition you need in problems about functions and sequences.

Remember: the number of operations grows with n according to the algorithm’s complexity — bubble sort $\sim n^2$, merge sort $\sim n\log n$ — and the difference escalates sharply with the data size. That is why the choice of algorithm, not a faster computer, decides what can be computed.