Lesson

Sorting Algorithms

Sorting arranges data in order. Algorithms differ in time complexity and in whether they are stable (preserving the relative order of equal keys). Comparison sorts cannot beat $O(n \\log n)$ in the worst case.

Practice

Q1

What is the time complexity of merge sort?

Show hint

Divide in half, then merge in linear time.

Q2

Which of these sorts is stable?

Show hint

The classic stable comparison sort.

Even fast algorithms have worst cases. The number of comparisons a simple scan needs is often one fewer than the number of items.

Quiz

Q1

How many comparisons are needed to find the maximum of $8$ numbers?

Show hint

Each comparison eliminates one candidate: $n - 1$.

Q2

What is the worst-case time of quicksort?

Show hint

A bad pivot degrades it to quadratic time.

Q3

How many adjacent comparisons check whether a list of $5$ items is already sorted?

Show hint

Compare each adjacent pair: $n - 1$ times.