Divide and Conquer P1
InsertionSort & MergeSort
Instructor: Yiran "Lawrence" Luo
Previously, in Asymptotic Notations
● Measuring the time complexity of an algorithm w.r.t the size of the input
● Big-O for the upper bound, Big-Omega for the lower bound, and Big-Theta for
the tight bound
○ How to invoke their definition formulas
These notations will be seen all over again throughout this course as we analyze
different more advanced algorithms, esp. Big-O.
For the sake of CS consistency, let's assume
an Array starts at index 0.
A[0] is the first element in array A by default,
unless specified otherwise.
The Incremental Insertion-Sort, to start with
1. At A[0], nothing is needed
2. Focus on A[1], where should its
value be in the subarray A[0] .. A[0]?
Swap all the way there.
3. Focus on A[2], where should its
value be in the subarray A[0] .. A[1]?
Swap all the way there.
4. …
Ref: https://thinkdiff.net/insertion-sort-swift-db14b9a79016
The Incremental Insertion-Sort, room for improvement
E.g. to move 1 from the tail to the head,
we need to swap (n-1) times, because
swapping with neighbors is incremental.
Is there a way to reduce this? Like leaping
ahead faster?
Ref: https://thinkdiff.net/insertion-sort-swift-db14b9a79016
ANS: O(N^2), when the given is in descending order.
Divide and Conquer Comes to Res- RECUR
1. Divide the problem into smaller sub-problems
2. Conquer the sub-problems by solving them recursively, or solve trivial
subproblems without recursion (the marginal/extreme cases).
3. Combine all the sub-solutions to the sub-problems from 2., and obtain a
whole solution to the original problem.
PS. Parallel computing / concurrence and
MapReduce both follow the same philosophy, in
different scales.
Pause and ponder, brb
MergeSort, one of the Embodiments of D&C, by default
Backbone Strategy of MergeSort
● Divide the input n-element sequence into two equal-length halves
● Recursion - Call Merge-Sort() individually on the two unsorted halves
○ We will end up possessing two sorted halves
●Merge()the two already sorted halves into one full sorted sequence of
n-elements
The marginal cases (which do not require recursive steps)
● If n less than 1: return as-is, a 0- or 1-element sequence is already sorted
Merge-Sort(), the top-down recurrent function pseudocode
MERGE-SORT(A, p, r) // Sorting the A[p..r] part of A[]
if p < r then {
q = floor((p + r)/2) // q is the middle index
MERGE-SORT(A, p, q)
MERGE-SORT(A, q+1, r)
MERGE2(A, p, q, r)
}
// To sort the entire array A, you pass in
MERGE-SORT(A, 0, length(A)-1)
MERGE2() - Merging Two Sorted Sequences, cont'd
while i < q and j < r do
if B[i] < B[j] then
A[z] = B[i]
i++
else
A[z] = B[j]
j++
z++
// Resembles what this GIF does. Use two
tracker indexes i, j and "pop"/overwrite
which ever is currently the smaller into A
Ref: https://www.codesdope.com/course/algorithms-merge-sort/
MERGE2() - Merging Two Sorted Sequences, cont'd
if i < q then
A[z..r] = B[i..q]
else if j < r
A[z..r] = B[j..r]
// Attach the remaining uncompared
sequence after whichever tracker
reaches the end of its subsequence
// A[p..r] has become sorted
// End of MERGE2()
MERGE2()is linear AKA O(r-p) or Θ(r-p),
or Θ(n) if the input size is not specified.
You pop exactly (r-p) items in total
Ref: https://www.codesdope.com/course/algorithms-merge-sort/
Pause and ponder, what's the time
complexity of the overall MergeSort?
In terms of Big-O.
Time to hydrate
Counting the # of ops
# of divides?
Counting the # of divide ops
# of divides?
You end up having every item on
their own, so O(n) divides.
n does not have to be a power of 2
Counting the # of combine ops
Merge every pair of 1-item
sequences, you need O(2) * (n/2) =
O(n) 'pop' operations
Counting the # of combine ops
Merge every pair of 2-item sorted
sequences, you need O(4) * (n/4) =
O(n) 'pop' operations
Counting the # of combine ops
… this is the final merge
Merge every pair of (n/2)-item
sorted sequences, you need O(n/2)
* (2) = O(n) 'pop' operations
Counting the # of all ops of substance
In total, you need log2(n) * O(n) =
O(n log n) 'pop' operations.
O(n) + O(n log n) = O(n log n) is
the time complexity of MergeSort
# of layers of recursion
Food for thought, why is the time complexity
of MergeSort Θ(n log n)?
We will continue on next Tue. into QuickSort
HW1 is online today. Due in 7 days.
