COMP20007 Design of Algorithms
Sorting – Part 2
Daniel Beck
Lecture 12
Semester 1, 2020
1
Mergesort
function Mergesort(A[0..n − 1]) if n > 1 then
B[0..�n/2� − 1] ← A[0..�n/2� − 1] C [0..�n/2� − 1] ← A[�n/2�..n − 1] Mergesort(B[0..�n/2� − 1]) Mergesort(C [0..�n/2� − 1]) Merge(B,C,A)
2
Mergesort – Merge function
function Merge(B [0..p − 1], C [0..q − 1], A[0..p + q − 1]) i ← 0; j ← 0; k ← 0
while i < p and j < q do
if B[i] ≤ C[j] then
A[k ] ← B [i ]; i ← i + 1
else
A[k ] ← C [j ]; j ← j + 1
k←k+1 if i ==p then
A[k..p + q − 1] ← C[j..q − 1] else
A[k..p + q − 1] ← B[i..p − 1]
3
Mergesort - Properties
Divide-and-Conquer algorithm
4
Mergesort - Properties
Divide-and-Conquer algorithm
• In contrast with decrease-and-conquer algorithms, such as Insertion Sort.
4
Mergesort - Properties
Divide-and-Conquer algorithm
• In contrast with decrease-and-conquer algorithms, such as
Insertion Sort. Questions!
4
Mergesort - Properties
Divide-and-Conquer algorithm
• In contrast with decrease-and-conquer algorithms, such as
Insertion Sort. Questions!
• In-place? (or does it require extra memory?) • Stable?
4
Mergesort - Properties
• In-place?
5
Mergesort - Properties
• In-place? No. (requires O(n) auxiliary array + O(log n) stack space for recursion)
• Stable?
5
Mergesort - Properties
• In-place? No. (requires O(n) auxiliary array + O(log n) stack space for recursion)
• Stable? Yes! (Merge keeps relative order with additional bookkeeping)
5
Mergesort - Complexity
• Worst case?
• Best case?
• Average case?
6
Mergesort
function Mergesort(A[0..n − 1]) if n > 1 then
B[0..�n/2� − 1] ← A[0..�n/2� − 1] C [0..�n/2� − 1] ← A[�n/2�..n − 1] Mergesort(B[0..�n/2� − 1]) Mergesort(C [0..�n/2� − 1]) Merge(B,C,A)
7
Mergesort – Complexity
8
Mergesort – In Practice
• Guaranteed Θ(n log n) complexity
• Highly parallelisable
• Multiway Mergesort: excellent for secondary memory
• Used in JavaScript (Mozilla)
• Basis for hybrid algorithms (TimSort: Python, Android)
Take-home message: Mergesort is an excellent choice if stability is required and the extra memory cost is
low.
9
Quicksort
function Quicksort(A[l ..r ]) if l < r then
s ← Partition(A[l..r]) Quicksort(A[l..s − 1]) Quicksort(A[s + 1..r ])
� Starts with A[0..n − 1]
10
Quicksort - Lomuto partitioning
function LomutoPartition(A[l..r]) p ← A[l]
s←l
for i ← l + 1 to r do
if A[i] < p then s←s+1
Swap(A[s ], A[i ])
Swap(A[l ], A[s ]) return s
11
Quicksort - Properties
Divide-and-Conquer algorithm
12
Quicksort - Properties
Divide-and-Conquer algorithm Questions!
12
Quicksort - Properties
Divide-and-Conquer algorithm Questions!
• In-place? • Stable?
12
Quicksort - Properties
• In-place?
13
Quicksort - Properties
• In-place? Yes, buy still requires O(log n) memory for the stack.
13
Quicksort - Properties
• In-place? Yes, buy still requires O(log n) memory for the stack.
• Stable?
13
Quicksort - Properties
• In-place? Yes, buy still requires O(log n) memory for the stack.
• Stable? No (non-local swaps)
13
Quicksort - Partitioning
• Lomuto partitioning can be used but not the best in pratice.
14
Quicksort - Partitioning
• Lomuto partitioning can be used but not the best in pratice.
• Instead, practical implementations use Hoare partitioning (proposed by the inventor of Quicksort).
14
Quicksort - Partitioning
• Lomuto partitioning can be used but not the best in pratice.
• Instead, practical implementations use Hoare partitioning (proposed by the inventor of Quicksort).
• How does it work? Let’s go back to my games first...
14
Quicksort - Hoare partitioning
function HoarePartition(A[l..r]) p ← A[l]
i ← l; j ← r + 1 repeat
repeat i ← i + 1 until A[i] ≥ p repeat j ← j − 1 until A[j] ≤ p Swap(A[i ], A[j ])
until i ≥ j Swap(A[i ], A[j ]) Swap(A[l ], A[j ]) return j
15
Quicksort - Complexity
• Worst case?
• Best case?
• Average case?
16
Quicksort - Complexity
• Worst case?
• Best case?
• Average case?
Warning: not trivial, but give it a go. 😉
16
Quicksort - Complexity
17
Quicksort - Complexity
18
Quicksort - In practice
• Used in C (qsort)
• Basis for C++ sort (Introsort)
• Fastest sorting algorithm in most cases
19
Quicksort - In practice
• Used in C (qsort)
• Basis for C++ sort (Introsort)
• Fastest sorting algorithm in most cases
Take-home message: Quicksort is the algorithm of choice when speed matters and stability is not required.
19
Summary so far
Selection Sort: Slow, but only O(n) key exchanges.
20
Summary so far
Selection Sort: Slow, but only O(n) key exchanges.
Insertion Sort: Very good for small arrays and when data is expected to be “almost sorted”.
20
Summary so far
Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is
expected to be “almost sorted”.
Mergesort: Better for mid-size arrays and when stability is required.
20
Summary so far
Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is
expected to be “almost sorted”.
Mergesort: Better for mid-size arrays and when stability is required.
Quicksort: Usually the best choice for large arrays, with excellent empirical performance and only
O(log n) memory cost.
20
Summary so far
Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is
expected to be “almost sorted”.
Mergesort: Better for mid-size arrays and when stability is required.
Quicksort: Usually the best choice for large arrays, with excellent empirical performance and only
O(log n) memory cost. Next lecture: Heapsort
20