Merge Sort and Quick Sort
Sorting
• Insertion sort
– Design approach: incremental
– Sorts in place: Yes
– Best case: Θ(n)
– Worst case: Θ
(n2)
• Bubble Sort
– Design approach: incremental
– Sorts in place: Yes
– Running time: Θ
(n2)
2
Sorting
• Selection sort
– Design approach: incremental
– Sorts in place: Yes
– Running time: Θ
(n2)
• Merge Sort
– Design approach: divide and conquer
– Sorts in place: No
– Running time: Let’s see!!
3
Divide-and-Conquer
• Divide the problem into a number of sub-problems
– Similar sub-problems of smaller size
• Conquer the sub-problems
– Solve the sub-problems recursively
– Sub-problem size small enough ⇒ solve the problems in
straightforward manner
• Combine the solutions of the sub-problems
– Obtain the solution for the original problem
4
Merge Sort Approach
• To sort an array A[p . . r]:
• Divide
– Divide the n-element sequence to be sorted into two
subsequences of n/2 elements each
• Conquer
– Sort the subsequences recursively using merge sort
– When the size of the sequences is 1 there is nothing
more to do
• Combine
– Merge the two sorted subsequences
5
Merge Sort
p q r
1 2 3 4 5 6 7 8
Alg.: MERGE-SORT(A, p, r)
5 2 4 7 1 3 2 6
if p < r check for base case
then q ← ⎣(p + r)/2⎦ Divide
MERGE-SORT(A, p, q) Conquer
MERGE-SORT(A, q + 1, r) Conquer
MERGE(A, p, q, r) Combine
• Initial call: MERGE-SORT(A, 1, n)
6
Example – n Power of 2
1 2 3 4 5 6 7 8
Divide 5 2 4 7 1 3 2 6 q=4
1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6
1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6
1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6
7
Example – n Power of 2
1 2 3 4 5 6 7 8
Conquer 1 2 2 3 4 5 6 7
and
Merge 1 2 3 4 5 6 7 8
2 4 5 7 1 2 3 6
1 2 3 4 5 6 7 8
2 5 4 7 1 3 2 6
1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6
8
Example – n Not a Power of 2
1 2 3 4 5 6 7 8 9 10 11
4 7 2 6 1 4 7 3 5 2 6 q=6
Divide
1 2 3 4 5 6 7 8 9 10 11
q=3 4 7 2 6 1 4 7 3 5 2 6 q=9
1 2 3 4 5 6 7 8 9 10 11
4 7 2 6 1 4 7 3 5 2 6
1 2 3 4 5 6 7 8 9 10 11
4 7 2 6 1 4 7 3 5 2 6
1 2 4 5 7 8
4 7 6 1 7 3
9
Example – n Not a Power of 2
1 2 3 4 5 6 7 8 9 10 11
Conquer 1 2 2 3 4 4 5 6 6 7 7
and
1 2 3 4 5 6 7 8 9 10 11
Merge 1 2 4 4 6 7 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11
2 4 7 1 4 6 3 5 7 2 6
1 2 3 4 5 6 7 8 9 10 11
4 7 2 1 6 4 3 7 5 2 6
1 2 4 5 7 8
4 7 6 1 7 3
10
Merge - Pseudocode
p q r
Alg.: MERGE(A, p, q, r) 1 2 3 4 5 6 7 8
2 4 5 7 1 2 3 6
1. Compute n1 and n2
2. Copy the first n1 elements into n1 L[1 . . nn12 +
1] and the next n2 elements into R[1 . . n2 + 1]
3. L[n1 + 1] ← ∞; R[n2 + 1] ← ∞ p q
4. i ← 1; j ← 1 L 2 4 5 7 ∞
5. for k ← p to r q+1 r
6. do if L[ i ] ≤ R[ j ] R 1 2 3 6 ∞
7. then A[k] ← L[ i ]
8. i ←i + 1
9. else A[k] ← R[ j ]
10. j←j+1
11
Complexity of Merge Sort
Algorithm:
mergesort( int [] a, int left, int right)
{
if (right > left)
{ middle = left + (right - left)/2;
mergesort(a, left, middle);
mergesort(a, middle+1, right);
merge(a, left, middle, right); }
}
Assumption: N is a power of two. For N = 1: time is a constant (denoted by 1)
Otherwise, time to mergesort N elements = time to mergesort N/2 elements + time to merge
two arrays each N/2 elements.
Time to merge two arrays each N/2 elements is linear, i.e. N
Thus we have:
(1) T(1) = 1
(2) T(N) = 2T(N/2) + N
Next we will solve this recurrence relation. First we divide (2) by N:
(3) T(N) / N = T(N/2) / (N/2) + 1
Complexity of Merge Sort
N is a power of two, so we can write
(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1
(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1
(6) T(N/8) / (N/8) = T(N/16) / (N/16) +1
(7) ……
(8) T(2) / 2 = T(1) / 1 + 1
Now we add equations (3) through (8) : the sum of their left-hand sides will be equal to
the sum of their right-hand sides:
T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 =
T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN
(LogN is the sum of 1s in the right-hand sides)
After crossing the equal term, we get
(9) T(N)/N = T(1)/1 + LogN
T(1) is 1, hence we obtain
(10) T(N) = N + NlogN = O(NlogN)
Hence the complexity of the MergeSort algorithm is O(NlogN).
Quicksort A[p…q]
≤ A[q+1…r]
• Sort an array A[p…r]
• Divide
– Partition the array A into 2 subarrays A[p..q] and A[q+1..r], such that
each element of A[p..q] is smaller than or equal to each element in
A[q+1..r]
– Need to find index q to partition the array
14
Quicksort A[p…q]
≤ A[q+1…r]
• Conquer
– Recursively sort A[p..q] and A[q+1..r] using Quicksort
• Combine
– Trivial: the arrays are sorted in place
– No additional work is required to combine them
– The entire array is now sorted
15
Recurrence
Alg.: QUICKSORT(A, p, r) Initially: p=1, r=n
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT (A, p, q)
QUICKSORT (A, q+1, r)
Recurrence:
T(n) = T(q) + T(n – q) + n
16
Partitioning the Array
Alg. PARTITION (A, p, r)
p r
1. x ← A[p]
A: 5 3 2 6 4 1 3 7
2. i ← p – 1
3. j ← r + 1 i j
4. while TRUE A[p…q] ≤ A[q+1…r]
5. do repeat j ← j – 1 A: ap ar
6. until A[j] ≤ x
7. do repeat i ← i + 1 j=q i
8. until A[i] ≥ x
Each element is
9. if i < j visited once!
10. then exchange A[i] ↔ A[j] Running time: Θ(n)
11. else return j n=r–p+1
17
Analysis of quicksort
Partition can be done in O(n) time, where n is the size of
the array. Let T(n) be the number of comparisons
required by Quicksort.
If the pivot ends up at position k, then we have
T(n) =T(n−k) + T(k −1) + n
To determine best-, worst-, and average-case complexity
we need to determine the values of k that correspond
to these cases.
Best-Case Complexity
● The best case is clearly when the pivot always
partitions the array equally.
● Intuitively, this would lead to a recursive depth of at
most lg n calls
● We can actually prove this. In this case
– T(n) ≈T(n/2) + T(n/2) + n ⇒ Θ(n lg n)
Best Case Partitioning
• Best-case partitioning
– Partitioning produces two regions of size n/2
• Recurrence: q=n/2
T(n) = 2T(n/2) + Θ(n)
T(n) = Θ(nlgn) (Master theorem)
Average-Case Complexity
Average case is rather complex, but is where the
algorithm earns its name. The bottom line is: T(n) =
Θ(nlgn)
Worst Case Partitioning
The worst-case behavior for quicksort occurs when the
partitioning routine produces one region with n - 1 elements and
one with only l element.
Let us assume that this n n
Unbalanced partitioning arises 1 n-1 n
at every step of the algorithm. 1 n-2 n-1
n 1 n-3 n-2
Since partitioning costs (n) time 1
2 3
and T(1) = (1), the recurrence for
1 1 2
the running time is
T(n) = T(n - 1) + (n). Θ(n2)
To evaluate this recurrence, we observe that T(1) = (1) and then
iterate:
Worst Case Partitioning
Best case: split in the middle — Θ( n log n)
Worst case: sorted array! — Θ( n2)
Average case: random arrays — Θ( n log n)