Merge Sort Lecture Notes

Introduction to Merge Sort

• Definition: Recursive sorting algorithm following divide and conquer strategy.
• Problem: Sorting a large list of elements.

Divide and Conquer Strategy

• Break larger problems into smaller subproblems.
• Solve the smaller problems and combine solutions to address the main problem.
• Condition for small problem: If the list has one element, it is already sorted.

Merge Sort Process

1. Parameters: Takes two parameters - beginning (low) and end (high) of the list.
2. Base Condition:
   • If low is equal to high, it signifies a single element (sorted).
   • If low is less than high, proceed with the following steps.
3. Finding the Middle:
   • Calculate mid as (low + high) / 2.
   • This splits the list into two subproblems: left and right.
4. Recursive Calls:
   • Perform merge sort on the left side (low to mid) and the right side (mid + 1 to high).
5. Merging:
   • Once both sides are sorted, merge the two sorted lists into one.

Example of Merge Sort Tracing

• Initial Call: mergeSort(1, 8) with 8 elements.
• Split into two halves till each half has one element.
• Merging occurs at each level (after splitting) to form sorted sublists.

Tracing Example

• First call to mergeSort(1, 4), then further split down to 1,1, 2,2, etc.
• Merges result:
  • [3, 9] then [3, 5, 7, 9]
• Right Side: mergeSort(5, 8) results into [2, 4, 6, 8].
• Finally, both parts are merged resulting in the entire sorted list: [2, 3, 4, 5, 6, 7, 8, 9].

Merge Sort Characteristics

• Merging happens at each level of recursion.
• It is categorized as a two-way merge sort due to merging two lists at once, following the divide and conquer approach.

Time Complexity Analysis

• Level Count: Each level has n merges, and therefore, total levels are logarithmic based on element count.
• Time Complexity:
  • Using Master Theorem for recurrence relation:
  • T(n) = 2T(n/2) + n
  • Solves to T(n) = Θ(n log n).

Conclusion

• Merge sort effectively sorts large lists by recursively breaking them down and merging sorted sublists.
• Provides efficient sorting with a time complexity of O(n log n).