Sorting has a floor: any comparison sort needs about n log n comparisons. The simple sorts are n squared, and the fast sorts reach the floor.
About 2 min of reading
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Measure the cost of sorting.
Compare n log n and n squared for 1000.
Before you run it, say out loud what it will print. Then open the answer.
Count pair comparisons for three.
Before you run it, say out loud what it will print. Then open the answer.
Confirm a sorted row is sorted.
Before you run it, say out loud what it will print. Then open the answer.
Compare growth for 100.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Any sort that only compares items cannot beat about n log n. The fast sorts reach that floor, so they are close to optimal.
Good sorts exploit runs already in order, so nearly sorted data is cheap. A simple sort does the same work regardless.
import math
print(round(1000 * math.log2(1000)))
print(1000 ** 2)A thousand items: about ten thousand steps for a good sort, one million for a simple one. The gap is huge.
import math
print(math.log2(8))With n items there are n factorial orders to tell apart. Each comparison splits that, so n log n comparisons are the least possible.
nums = [3, 1, 2]
cmps = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
cmps += 1
print(cmps)A simple sort compares every pair, about n squared. A good sort compares far fewer.
import time
nums = list(range(1000))
print(nums == sorted(nums))An already sorted row is the fast case for good sorts. They detect runs already in order.
nums = list(range(5, 0, -1))
print(nums)A reversed row is the hard case for some sorts and the easy case for others. Input shape changes the cost.
rows = [(2, "a"), (2, "b")]
print(sorted(rows))Keeping ties in order takes a touch more work. That is why some sorts drop stability.
import bisect
nums = sorted([9, 1, 5, 3])
print(bisect.bisect_left(nums, 5))One sort then many cheap searches. Sorting pays once and makes each ask log n.
import math
print(round(100 * math.log2(100)))
print(100 ** 2)A hundred items: about seven hundred versus ten thousand. The better curve grows slower as n rises.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.