1 of 18

Comparison Sorts

Optimizing selection sort, analyzing sorting algorithm stability, and quantifying sortedness.

1

Kevin Lin, with thanks to many others.

2 of 18

Selection Sort Stability

Find the smallest item in the array, and swap it with the first item.
Find the second smallest item in the array, and swap it with the second item.
Continue until all items in the array are sorted.

Selection sort is not stable (though it still returns a correct sort). Give an example.

2

Q

1

3 of 18

Selection Sort Stability

Find the smallest item in the array, and swap it with the first item.
Find the second smallest item in the array, and swap it with the second item.
Continue until all items in the array are sorted.

Selection sort is not stable (though it still returns a correct sort). Give an example.

What is stability? If we have 1_A == 1_B, then in a stable sort 1_A must come before 1_B

Long-distance swap is dangerous. Stability only matters for reference types (e.g. objects).

3

A

0_A

0_B

1_B

1_A

4 of 18

Heapifying

Give the result of bottom-up max-heapifying the array [9, 1, 1, 3, 5, 5, 6, 8].

4

Q

5 of 18

Heapifying

Give the result of bottom-up max-heapifying the array [9, 1, 1, 3, 5, 5, 6, 8].

Heapsort

Bottom-up max-heapification. Come up with a counterexample or use heap invariants.

Repeatedly sink from the bottom-up.
Repeatedly sink from the top-down: sinking into the void.
Repeatedly swim from the bottom-up: counterexample.
Repeatedly swim from the top-down.�This is correct but slower.

5

A

8

9

3

6

5

1

3

2

6 of 18

Recursive Merge Sorting

Give the two arrays that will be merged by the final step of merge sort on [9, 1, 1, 3, 5, 5, 6, 8].

6

Q

7 of 18

Recursive Merge Sorting

Give the two arrays that will be merged by the final step of merge sort on [9, 1, 1, 3, 5, 5, 6, 8].

Merge sort is a recursive procedure! Not necessary to simulate the sorting algorithm.

mergeSort([9, 1, 1, 3]) = [1, 1, 3, 9]
mergeSort([5, 5, 6, 8]) = [5, 5, 6, 8]
merge([1, 1, 3, 9], [5, 5, 6, 8]) = [1, 1, 3, 5, 5, 6, 8, 9]

7

A

8 of 18

Insertion Sort

Unstable sorting algorithms (selection sort, heapsort) use long-distance swaps.

Merge sort, a stable sort, uses the fact that left-half items come before right-half items.

Idea. Build a sorted subsection but use only left-neighbor swaps to maintain stability.

Insertion sort. Scan from left to right…

If an item is out of order with respect to its left-neighbor, swap left.
Keep on swapping left until the item is in order with respect to its left-neighbor.

8

32,15,2,17,19,26,41,17,17

9 of 18

Insertion Sort Examples

9

P O T A T O

P O T A T O (0 swaps)

O P T A T O (1 swap )

O P T A T O (0 swaps)

A O P T T O (3 swaps)

A O P T T O (0 swaps)

A O O P T T (3 swaps)

S O R T E X A M P L E

S O R T E X A M P L E (0 swaps)

O S R T E X A M P L E (1 swap )

O R S T E X A M P L E (1 swap )

O R S T E X A M P L E (0 swaps)

E O R S T X A M P L E (4 swaps)

E O R S T X A M P L E (0 swaps)

A E O R S T X M P L E (6 swaps)

A E M O R S T X P L E (5 swaps)

A E M O P R S T X L E (4 swaps)

A E L M O P R S T X E (7 swaps)

A E E L M O P R S T X (8 swaps)

Purple Item that we’re swapping left.

Black Item swapped with purple item.

Grey Not considered this iteration.

Algorithms (Robert Sedgewick, Kevin Wayne/Princeton)

10 of 18

Inversions: Quantifying Sortedness

Inversion. A pair of keys that are out of order.

Partially sorted. An array of length N is partially sorted if the number of inversions is in O(N).

A sorted array has 0 inversions.
A reverse-sorted array has about ½N² inversions.

Each local swap fixes 1 inversion. Insertion sort runtime is in Θ(N + K) with K inversions.

10

A E E L M O T R X P S

1	2	3	4	5	6
T–R	T–P	T–S	R–P	X–P	X–S

COS 226: Elementary Sorts (Robert Sedgewick, Kevin Wayne/Princeton)

11 of 18

Worst-Case Inversions

If we add 10 unknown items to the end of a sorted array, at most how many inversions can there be in the array?

11

Q

12 of 18

Worst-Case Inversions

If we add 10 unknown items to the end of a sorted array, at most how many inversions can there be in the array?

Situation: worst-case when unknown items are in reverse order.

Within these 10 items, how many inversions are there? 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

What if the unknown items are actually smaller than the sorted part of the array?

Potentially have to move these 10 unknown items up the front of the array.

Suppose sorted part is size N.

Then moving the first of the 10 unknown items is N inversions.
Same pattern with other items. 10N inversions.

10N + 45 inversions total.

12

A

13 of 18

Monotonically-Improving

For each algorithm, can the inversion count increase at some point in its execution?

Insertion sort.

Selection sort.

Bottom-up max-heapification.

Bottom-up min-heapification.

Merge sort.

13

Q

14 of 18

Monotonically-Improving

For each algorithm, can the inversion count increase at some point in its execution?

What does it mean to increase inversion count? We start at some inversion count and then want to make sure it doesn’t increase.

Insertion sort. Doesn’t increase. “Each local swap fixes 1 inversion.”

Selection sort. Doesn’t increase. Find the min item each time and moves it up to the front.

Note: when thinking about heaps, we’re looking at it from the array perspective.

Bottom-up max-heapification. Increases inversions: take a sorted array and then max-heap.

Bottom-up min-heapification. Doesn’t increase. Min-heap invariant when sinking.

Merge sort. Doesn’t increase, each merging either maintains inversion count or decreases it.

14

A

15 of 18

15

Sort	Best-Case	Worst-Case	Space	Stable	Notes
Selection sort	Θ(N²)	Θ(N²)	Θ(1)	No
Heapsort	Θ(N)	Θ(N log N)	Θ(1)	No	Slow in practice.
Merge sort	Θ(N log N)	Θ(N log N)	Θ(N)	Yes	Fastest stable sort.
Insertion sort	Θ(N)	Θ(N²)	Θ(1)	Yes	Best for small or almost sorted inputs.

16 of 18

Shellsort: Optimizing Insertion Sort (Optional)

Idea. Fix multiple inversions at once.

Stride. Instead of comparing adjacent items, compare items that are h apart.

Shellsort. Perform multiple, partial insertion sorts with different strides.

Start with large stride and decrease towards 1, e.g. h = 7, then h = 3, and then h = 1.

Insertion sort is shellsort with one stride, h = 1.

16

M O R T E X A S P L E

h = 7

Algorithms (Robert Sedgewick, Kevin Wayne/Princeton)

S O R T E X A M P L E

h = 3

17 of 18

Shellsort: Three Iterations of Partial Insertion Sort

17

Algorithms (Robert Sedgewick, Kevin Wayne/Princeton)

S O R T E X A M P L E

M O R T E X A S P L E (1 swap, >1 inversions)

M O R T E X A S P L E (0 swaps, 0 inversions)

M O L T E X A S P R E (1 swap, >1 inversions)

M O L E E X A S P R T (1 swap, >1 inversions)

M O L E E X A S P R T

E O L M E X A S P R T (1 swap, >1 inversions)

E E L M O X A S P R T (1 swap, >1 inversions)

E E L M O X A S P R T (0 swaps, 0 inversions)

A E L E O X M S P R T (2 swaps, >1 inversions)

A E L E O X M S P R T (0 swaps, 0 inversions)

A E L E O P M S X R T (1 swaps, >1 inversions)

A E L E O P M S X R T (0 swaps, 0 inversions)

h = 7

h = 3

A E L E O P M S X R T

A E E L O P M S X R T

A E E L M O P S X R T

A E E L M O P R S X T

A E E L M O P R S T X

h = 1

18 of 18

18

Sort	Best-Case	Worst-Case	Space	Stable	Notes
Selection Sort	Θ(N²)	Θ(N²)	Θ(1)	No
Heapsort	Θ(N)	Θ(N log N)	Θ(1)	No	Slow in practice.
Merge Sort	Θ(N log N)	Θ(N log N)	Θ(N)	Yes	Fastest stable sort.
Insertion Sort	Θ(N)	Θ(N²)	Θ(1)	Yes	Best for small or almost sorted inputs.
Shellsort	Θ(N)	Ω(N log N)	Θ(1)	No	Optional for this course.