This week we covered merge sort as an example of the divide-and-conquer technique. Since much of the week went to reviewing for the midterm, merge sort was the only new algorithm we learned.
Divide-and-conquer has three steps:
- Divide the problem into smaller subproblems of the same type
- Conquer (solve) each subproblem recursively
- Combine the subproblem solutions into a solution for the original problem
Merge sort works by dividing an array into two halves, sorting each half recursively, and then merging the two sorted halves back together. An important point is that the two halves must be sorted before they can be merged.
But how do we sort the two halves? By using merge sort! This is the recursive step. The base case is an array with only one element, which is already sorted by definition.
Applying the divide-and-conquer technique to merge sort:
- Divide: Split the array into two approximately equal subarrays
- Conquer: Recursively sort each subarray using merge sort
- Combine: Merge the two sorted subarrays into a single sorted array
Here is an example implementation of merge sort on Python Tutor. Notice that the comparison uses <=. This means that the element from the left half goes first when both elements are equal, which makes merge sort a stable sort, since equal elements keep their original order.
Merge sort divides the input in half at each level of recursion, producing about log₂ n levels. At each level, merging the two halves takes linear time, giving merge sort a time complexity of Θ(n log(n)).