3 of 72

Sorts So Far

	Best Case Runtime	Worst Case Runtime	Space	Demo	Notes
Selection Sort	Θ(N²)	Θ(N²)	Θ(1)	Link
Heapsort (in place)	Θ(N)*	Θ(N log N)	Θ(1)	Link	Bad cache (61C) performance.
Mergesort	Θ(N log N)	Θ(N log N)	Θ(N)	Link	Fastest of these.
Insertion Sort (in place)	Θ(N)	Θ(N²)	Θ(1)	Link	Best for small N or almost sorted.

See this link for bonus slides on Shell's Sort, an optimization of insertion sort.

4 of 72

The Core Idea of Tony’s Sort: Partitioning

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.

Which partitions are valid?

550

330

550

330

550

330

550

330

Called the ‘pivot’.

5 of 72

Partition Sort, a.k.a. Quicksort

Observations:

5 is “in its place.” Exactly where it’d be if the array were sorted.
Can sort two halves separately, e.g. through recursive use of partitioning.

Q: How would we use this operation for sorting?

6 of 72

Job Interview Style Question (Partitioning)

Given an array of colors where the 0th element is white (and maybe a few more), and the remaining elements are red (less) or blue (greater), rearrange the array so that all red squares are to the left of the white square, the white squares end up together, and all blue squares are to the right. Your algorithm must complete in Θ(N) time (no space restriction).

Relative order of red and blues does NOT need to stay the same.

Example of a valid output

Another example of a valid output

Input

7 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item.
Quicksort left half.
Quicksort right half.

Input:

unsorted

8 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item (32).
Quicksort left half.
Quicksort right half.

Input:

partition(32)

9 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item (32).
Quicksort left half.
Quicksort right half.

Input:

<= 32

>= 32

in its place

partition(32)

10 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half.
Quicksort right half.

Input:

in its place

partition(32)

11 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half (details not shown).
Quicksort right half.

partition(32)

partition(15)

partition(2)

partition(17)

partition(19)

partition(17)

partition(26)

Input:

in its place

12 of 72

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half (details not shown).
Quicksort right half (details not shown).

partition(32)

partition(15)

partition(2)

partition(17)

partition(19)

partition(17)

partition(26)

Input:

in its place

If you don't fully trust the recursion, see these extra slides for a complete demo.

13 of 72

Partition Sort, a.k.a. Quicksort

Quick sorting N items:

Partition on leftmost item.
Quicksort left half.
Quicksort right half.

partition(32)

<= 32

>= 32

in its place

14 of 72

Quicksort

Quicksort was the name chosen by Tony Hoare for partition sort.

For most common situations, it is empirically the fastest sort.

Tony was lucky that the name was correct.

How fast is Quicksort? Need to count number and difficulty of partition operations.

Theoretical analysis:

Partitioning costs Θ(K) time, where Θ(K) is the number of elements being partitioned (as we saw in our earlier “interview question”).
The interesting twist: Overall runtime will depend crucially on where pivot ends up.

15 of 72

Quicksort Runtime Analysis

Lecture 32, CS61B, Spring 2025

Quicksort

Quicksort

Quicksort Runtime Analysis

Quicksort Runtime Analysis
Avoiding Quicksort Worst Case

Quicksort Variants

Philosophies for Avoiding Worst Case Behavior
Hoare Partitioning

Quick Select (median finding)

16 of 72

Best Case: Pivot Always Lands in the Middle

Only size 1 problems remain, so we’re done.

17 of 72

Best Case Runtime?

What is the best case runtime?

Only size 1 problems remain, so we’re done.

18 of 72

Best Case Runtime?

Only size 1 problems remain, so we’re done.

Total work at each level:

≈ N

≈N/2 + ≈N/2 = ≈N

≈N/4 * 4 = ≈N

Overall runtime:

Θ(NH) where H = Θ(log N)

so: Θ(N log N)

19 of 72

Worst Case: Pivot Always Lands at Beginning of Array

Give an example of an array that would follow the pattern to the right.

What is the runtime Θ(∙)?

20 of 72

Worst Case: Pivot Always Lands at Beginning of Array

Give an example of an array that would follow the pattern to the right.

1 2 3 4 5 6

What is the runtime Θ(∙)?

21 of 72

Quicksort Performance

Theoretical analysis:

Best case: Θ(N log N)
Worst case: Θ(N²)

Compare this to Mergesort.

Best case: Θ(N log N)
Worst case: Θ(N log N)

Recall that Θ(N log N) vs. Θ(N²) is a really big deal. So how can Quicksort be the fastest sort empirically? Because on average it is Θ(N log N).

Rigorous proof requires probability theory + calculus, but intuition + empirical analysis will hopefully convince you.

22 of 72

Argument #1: 10% Case

Suppose pivot always ends up at least 10% from either edge (not to scale).

Work at each level: O(N)

Runtime is O(NH).

H is approximately log _10/9 N = O(log N)

Overall: O(N log N).

N/10

9N/10

N/100

9N/100

81N/100

Punchline: Even if you are unlucky enough to have a pivot that never lands anywhere near the middle, but at least always 10% from the edge, runtime is still O(N log N).

23 of 72

Argument #2: Quicksort is BST Sort

Key idea: compareTo calls are same for BST insert and Quicksort.

Every number gets compared to 5 in both.
3 gets compared to only 1, 2, 4, and 5 in both.

Reminder: Random insertion into a BST takes O(N log N) time.

24 of 72

Empirical Quicksort Runtimes

For N items:

Mean number of compares to complete Quicksort: ~2N ln N
Standard deviation:

For more, see: http://www.informit.com/articles/article.aspx?p=2017754&seqNum=7

Empirical histogram for quicksort compare counts (10,000 trials with N = 1000)

Lots of arrays take 12,000ish compares to sort with Quicksort.

A very small number take 15,000ish compares to sort with Quicksort.

Chance of taking 1,000,000ish compares is effectively zero.

25 of 72

Quicksort Performance

Theoretical analysis:

Best case: Θ(N log N)
Worst case: Θ(N²)
Randomly chosen array case: Θ(N log N) expected

Compare this to Mergesort.

Best case: Θ(N log N)
Worst case: Θ(N log N)

Why is it faster than mergesort?

Requires empirical analysis. No obvious reason why.

With extremely high probability!!

For our pivot/partitioning strategies: Sorted or close to sorted.

26 of 72

Sorting Summary (so far)

Listed by mechanism:

Selection sort: Find the smallest item and put it at the front.
Insertion sort: Figure out where to insert the current item.
Merge sort: Merge two sorted halves into one sorted whole.
Partition (quick) sort: Partition items around a pivot.

Listed by memory and runtime:

	Memory	Time	Notes
Heapsort	Θ(1)	Θ(N log N)	Bad caching (61C)
Insertion	Θ(1)	Θ(N²)	Θ(N) if almost sorted
Mergesort	Θ(N)	Θ(N log N)
Quicksort	Θ(log N) (call stack)	Θ(N log N) expected	Fastest sort

27 of 72

More Quicksort Origins

Amusingly, Quicksort was the wrong tool for the job. Two issues:

Language that Tony was using didn’t support recursion (so he couldn’t easily implement Quicksort).
Sentences are usually shorter than 15 words (So insertion sort is faster).

28 of 72

Philosophies for Avoiding Worst Case Quicksort Behavior

Lecture 32, CS61B, Spring 2025

Quicksort

Quicksort

Quicksort Runtime Analysis

Quicksort Runtime Analysis
Avoiding Quicksort Worst Case

Quicksort Variants

Philosophies for Avoiding Worst Case Behavior
Hoare Partitioning

Quick Select (median finding)

29 of 72

Partition Sort, a.k.a. Quicksort

Quicksorting N items: (Demo)

Partition on leftmost item.
Quicksort left half.
Quicksort right half.

partition(32)

<= 32

>= 32

in its place

Run time is Θ(N log N) in the best case, Θ(N²) in the worst case, and Θ(N log N) in the average case.

30 of 72

Avoiding the Worst Case: Question from Last Time

If pivot always lands somewhere “good”, Quicksort is Θ(N log N). However, the very rare Θ(N²) cases do happen in practice, e.g.

What specific array inputs yield bad Quicksort runtime?

Recall, our version of Quicksort has the following properties:

Leftmost item is always chosen as the pivot.
Our partitioning algorithm preserves the relative order of <= and >= items.

31 of 72

Avoiding the Worst Case: Question from Last Time

If pivot always lands somewhere “good”, Quicksort is Θ(N log N). However, the very rare Θ(N²) cases do happen in practice, e.g.

Bad ordering: Array already in sorted order (or almost sorted order).
Bad elements: Array with all duplicates (when using Hoare Partitioning; see next section).

What can we do to avoid worst case behavior?

Recall, our version of Quicksort has the following properties:

Leftmost item is always chosen as the pivot.
Our partitioning algorithm preserves the relative order of <= and >= items.

32 of 72

Avoiding the Worst Case: My Answers

What can we do to avoid running into the worst case for QuickSort?

Four philosophies:

1. Randomness: Pick a random pivot or shuffle before sorting.

2. Smarter pivot selection: Calculate or approximate the median.

3. Introspection: Switch to a safer sort if recursion goes to deep.

4. Preprocess the array: Could analyze array to see if Quicksort will be slow. No obvious way to do this, though (can’t just check if array is sorted, almost sorted arrays are almost slow).

33 of 72

Philosophy 1: Randomness (My Preferred Approach)

If pivot always lands somewhere “good”, Quicksort is Θ(N log N). However, the very rare Θ(N²) cases do happen in practice, e.g.

Bad ordering: Array already in sorted order.
Bad elements: Array with all duplicates.

Dealing with bad ordering:

Strategy #1: Pick pivots randomly.
Strategy #2: Shuffle before you sort.

The second strategy requires care in partitioning code to avoid Θ(N²) behavior on arrays of duplicates.

Common bug, even in a well known 2010s textbook.

34 of 72

Philosophy 2a: Smarter Pivot Selection (constant time pivot pick)

Randomness is necessary for best Quicksort performance! For any pivot selection procedure that is:

Deterministic
Constant Time

Dangerous input

The resulting Quicksort has a family of dangerous inputs that an adversary could easily generate.

See McIlroy’s “A Killer Adversary for Quicksort”

35 of 72

Philosophy 2b: Smarter Pivot Selection (linear time pivot pick)

Could calculate the actual median in linear time.

“Exact median Quicksort” is safe: Worst case Θ(N log N), but it is slower than Mergesort.

Raises interesting question though: How do you compute the median of an array? Will talk about how to do this later today.

36 of 72

Philosophy 3: Introspection

Can also simply watch your recursion depth.

If it exceeds some critical value (say 10 ln N), switch to mergesort.

Perfectly reasonable approach, though not super common in practice.

37 of 72

Sorting Summary (so far)

Listed by mechanism:

Selection sort: Find the smallest item and put it at the front.
Insertion sort: Figure out where to insert the current item.
Merge sort: Merge two sorted halves into one sorted whole.
Partition (quick) sort: Partition items around a pivot.

Listed by memory and runtime:

	Memory	Time	Notes
Heapsort	Θ(1)	Θ(N log N)	Bad caching (61C)
Insertion	Θ(1)	Θ(N²)	Θ(N) if almost sorted
Mergesort	Θ(N)	Θ(N log N)
Random Quicksort	Θ(log N) expected	Θ(N log N) expected	Fastest sort

38 of 72

Hoare Partitioning

Lecture 32, CS61B, Spring 2025

Quicksort

Quicksort

Quicksort Runtime Analysis

Quicksort Runtime Analysis
Avoiding Quicksort Worst Case

Quicksort Variants

Philosophies for Avoiding Worst Case Behavior
Hoare Partitioning

Quick Select (median finding)

39 of 72

Quicksort Flavors

We said Quicksort is the fastest, but this is only true if we make the right decisions about:

Pivot selection.
Partition algorithm.
How we deal with avoiding the worst case (can be covered by the above choices).

Suppose we run a speed test of Mergesort vs. Quicksort from last time, which had:

Pivot selection: Always use leftmost.
Partition algorithm: Make an array copy then do three scans for red, white, and blue items.
Shuffle before starting (to avoid worst case).

We’ll call this Quicksort L3S

40 of 72

Quicksort vs. Mergesort

Quicksort didn’t do so well!

	Pivot Selection Strategy	Partition Algorithm	Worst Case Avoidance Strategy	Time to sort 1000 arrays of 10000 ints
Mergesort	N/A	N/A	N/A	1.3 seconds
Quicksort L3S	Leftmost	3-scan	Shuffle	3.2 seconds

Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.

41 of 72

Tony Hoare’s In-place Partitioning Scheme

Tony originally proposed a scheme where two pointers walk towards each other.

Left pointer loves small items.
Right pointer loves large items.
Big idea: Walk towards each other, swapping anything they don’t like.

End result is that things on left are “small” and things on the right are “large”.

(Note: The demo we'll show is not the exact scheme Tony used)

Using this partitioning scheme yields a very fast Quicksort.

Though faster schemes have been found since.
Overall runtime still depends crucially on pivot selection strategy!

42 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

43 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Hello, lovely 15.

44 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Grrr…… 19

45 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap.

Input:

I dislike 17.

46 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Time to swap.

47 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Swapped.

48 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Immediate trouble.

49 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.

When pointers cross, you are done.

Input:

Trouble here, too.

50 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

Time to swap.

51 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

Swapped!

52 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

2 is cool.

53 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

26 is grossly large.

54 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

41 is fine.

55 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

26 is fine.

56 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

2 is no good… also hi L!!

57 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

2 is no good… also hi L!!

58 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

Time to swap.

59 of 72

Hoare Partitioning

Create L and G pointers at left and right ends.

L pointer is a friend to small items, and hates large or equal items.
G pointer is a friend to large items, and hates small or equal items.
Walk pointers towards each other, stopping on a hated item.

When both pointers have stopped, swap and move pointers by one.
When pointers cross, you are done walking.

Swap pivot with G.

Input:

Old pivot.

New pivot.

Swapped.

60 of 72

Quicksort vs. Mergesort

Using Tony Hoare’s two pointer scheme, Quicksort is better than mergesort!

More recent pivot/partitioning schemes do somewhat better.

Best known Quicksort uses a two-pivot scheme.
Interesting note, this version of Quicksort was introduced to the world by a previously unknown guy, in a Java developers forum (Link).

	Pivot Selection Strategy	Partition Algorithm	Worst Case Avoidance Strategy	Time to sort 1000 arrays of 10000 ints
Mergesort	N/A	N/A	N/A	1.3 seconds
Quicksort L3S	Leftmost	3-scan	Shuffle	3.2 seconds
Quicksort LTHS	Leftmost	Tony Hoare	Shuffle	0.9 seconds

Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.

61 of 72

Quick Select (median finding)

Lecture 32, CS61B, Spring 2025

Quicksort

Quicksort

Quicksort Runtime Analysis

Quicksort Runtime Analysis
Avoiding Quicksort Worst Case

Quicksort Variants

Philosophies for Avoiding Worst Case Behavior
Hoare Partitioning

Quick Select (median finding)

62 of 72

What If We Don’t Want Randomness?

Our approach so far: Use randomness to avoid worst case behavior, but some people don’t like having randomness in their sorting routine.

Another approach: Use the median (or an approximation) as our pivot.

Four philosophies:

1. Randomness: Pick a random pivot or shuffle before sorting.

2. Smarter pivot selection: Calculate or approximate the median.

3. Introspection: Switch to a safer sort if recursion goes to deep.

4. Try to cheat: If the array is already sorted, don’t sort (this doesn’t work).

This is what we’ve been using.

63 of 72

Philosophy 2a: Smarter Pivot Selection (linear time pivot pick)

The best possible pivot is the median.

Splits problem into two problems of size N/2.

Obvious approach: Just calculate the actual median and use that as pivot.

But how?

Goal: Come up with an algorithm for finding the median of an array. Bonus points if your algorithm takes linear time.

64 of 72

Philosophy 2a: Smarter Pivot Selection (linear time pivot pick)

Goal: Come up with an algorithm for finding the median of an array. Bonus points if your algorithm takes linear time.

Sort the array, return the middle item. Takes Θ(N log N) time to sort, though.

65 of 72

The Selection Problem

Computing the exact median would be great for picking an item to partition around. Gives us a “safe quick sort”.

However, it turns out that partitioning can be used to find the exact median.

The resulting algorithm is the best known median identification algorithm.

66 of 72

Quick Select

Goal, find the median:

Partition, pivot lands at 2.

Not the median. Why?
So what next?

Now pivot lands at 6.

Not the median.

Partition right subproblem, median can’t be to the left!

Pivot lands at 4. Are we done?

Yep, 9/2 = 4.

550

330

817

913

330

550

817

913

550

330

817

913

550

330

817

913

330

67 of 72

Worst case performance?

What is the worst case performance for Quick Select? Give an array that causes this worst case (assuming we always pick leftmost item as pivot).

68 of 72

Worst case performance?

What is the worst case performance for Quick Select? Give an array that causes this worst case (assuming we always pick leftmost item as pivot).

Worst asymptotic performance Θ(N²) occurs if array is in sorted order.

[1 2 3 4 5 6 7 8 9 10 … N]

…

[1 2 3 4 5 … N/2 … N]

69 of 72

Expected Performance

On average, Quick Select will take Θ(N) time.

Intuitive picture (not a proof!):

~N compares

~N/2 compares

~N/4 compares

On average, pivot ends up about halfway

N + N/2 + N/4 + … + 1 = Θ(N)

70 of 72

Quicksort With Quickselect?

What if we used Quickselect to find the exact median?

Resulting algorithm is very slow. Doesn't fix the worst case runtime issue
A little strange to do a bunch of partitions to identify the optimal item to partition around.

	Pivot Selection Strategy	Partition Algorithm	Worst Case Avoidance Strategy	Time to sort 1000 arrays of 10000 ints	Worst Case
Mergesort	N/A	N/A	N/A	1.3 seconds	Θ(N log N)
Quicksort L3S	Leftmost	3-scan	Shuffle	3.2 seconds	Θ(N²)
Quicksort LTHS	Leftmost	Tony Hoare	Shuffle	0.9 seconds	Θ(N²)
Quicksort QSTH	QuickSelect	Tony Hoare	Exact Median	4.9 seconds	Θ(N²)

71 of 72

Median Identification

Is it possible to find the median in Θ(N) time?

Yes! Use ‘BFPRT’ (called PICK in original paper).
Algorithm developed in 1972
In practice, rarely used.

Historical note: The authors of this paper include FOUR Turing Award winners (and Vaughan Pratt)

Let’s see how Exact Median Quicksort performs.

72 of 72

Quicksort vs. Mergesort

Quicksort using PICK to find the exact median (Quicksort PickTH) is terrible!

Cost to compute medians is too high.
Have to live with worst case Θ(N²) if we want good practical performance.

	Pivot Selection Strategy	Partition Algorithm	Worst Case Avoidance Strategy	Time to sort 1000 arrays of 10000 ints	Worst Case
Mergesort	N/A	N/A	N/A	1.3 seconds	Θ(N log N)
Quicksort L3S	Leftmost	3-scan	Shuffle	3.2 seconds	Θ(N²)
Quicksort LTHS	Leftmost	Tony Hoare	Shuffle	0.9 seconds	Θ(N²)
Quicksort PickTH	Exact Median	Tony Hoare	Exact Median	~15 seconds	Θ(N log N)

Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.