2.7.2. Merge Sort Algorithm
Introduction to Merge Sort
In this section, we learn about merge sort, a recursive divide and conquer algorithm used for sorting large lists.
Merge Sort Algorithm
- The merge sort algorithm takes two parameters, the beginning and ending of a list.
- If there is only one element in the list, it is already sorted. Otherwise, the list is divided into two subproblems by finding the middle index.
- Recursively perform merge sort on both subproblems.
- Once both subproblems are sorted, they are merged together using the merge procedure.
Tracing Merge Sort Algorithm
- To trace the merge sort algorithm, we start with an example list of 8 elements and pass it to the merge sort function with low as 1 and high as 8.
- The function finds the middle index and recursively calls itself on each half until each subproblem has only one element.
- The single-element subproblems are then merged together until all elements are sorted.
Key Takeaways
- Merge sort is a recursive divide and conquer algorithm used for sorting large lists.
- The algorithm divides a list into smaller subproblems until each subproblem has only one element.
- The single-element subproblems are then merged together using the merge procedure.
Merge Sort Algorithm
In this section, the speaker explains how merge sort works and compares it to two-way merge sort. They also discuss the time complexity of merge sort.
How Merge Sort Works
- Merge sort divides an array into smaller pieces until it reaches one element, then starts merging them.
- It is a divide-and-conquer algorithm that recursively splits and merges lists.
- The time complexity of merge sort is Theta(n log n).
Comparison with Two-Way Merge Sort
- Merge sort is similar to two-way merge sort but uses a different approach.
- While two-way merge sort merges two lists at a time, merge sort can recursively divide and merge multiple lists.
- As a result, merge sort is also called "more" sort.
Time Complexity of Merge Sort
- The time taken by merge sort can be calculated using the recursion tree method.
- The number of levels in the tree is log(n), where n is the number of elements in the list.
- Therefore, the time complexity of merge sort is Theta(n log n).
Example of Merge Sort Algorithm
In this section, the speaker provides an example to demonstrate how merge-sort works.
Example
- Given an array [1, 8], we find mid as (low+high)/2 = (1+8)/2 = 4. We then call merge-sort on the left-hand side [1, 4].
- We repeat this process until we have single-element arrays.
- We then start merging the arrays in pairs until we get a sorted array.
Time Complexity of Example
- The time complexity of this example is also Theta(n log n).
- The final sorted array is [1, 2, 4, 6, 8].
Tracing and Time Complexity
In this section, the speaker explains how tracing works in merge sort using a binary tree and post-order traversal. They then prepare a recurrence relation to find out the time complexity of merge sort.
Tracing in Merge Sort
- The tracing tree is more like a binary tree.
- Traversal is done using post-order: first left, left, left, then right, then root; merge root March.
- Merging is done in post-order traversal.
Recurrence Relation for Time Complexity
- If the algorithm takes T(n) time, ignoring conditions:
- Calculating mid takes T(n/2) time.
- Calling itself twice takes 2T(n/2) time.
- Merging n elements takes n time.
- Recurrence relation: T(n) = 2T(n/2) + n when n > 1; T(1) = 1.
Time Complexity Calculation
- Using Master's theorem:
- a = 2 (from two recursive calls).
- b = 2 (from dividing list into two halves).
- f(n) = n (from merging).
- log_b(a) = log_2(2) = 1
- f(n)log_b(a)^k = nlog_2(2)^1 = n
- Therefore, time complexity of merge sort is O(n*logn).