Merge Sort Algorithm Lecture Notes

Introduction to Merge Sort

Definition: Merge sort is a sorting algorithm that uses the divide and conquer technique.
Basic Concept: The algorithm splits an array into two subgroups and sorts those subgroups.

Splitting the Array:
- Start with an array size of n = 7 (e.g., [70, 20, 30, 40, 10, 50, 60]).
- Split the array into two subgroups:
  - Left side with 4 elements: [70, 20, 30, 40]
  - Right side with 3 elements: [10, 50, 60]
Recursive Splitting:
- Each subgroup continues to be split until there are single elements (base case).
- Example of splitting:
  - Left part: [70, 20, 30, 40] → [70, 20] and [30, 40]
  - Right part: [10, 50, 60] → [10, 50] and [60]
- Keep splitting until individual elements are reached.
Merging:
- Combine the single elements back into sorted order.
- Example:
  - Combine [70] and [20] → [20, 70]
  - Combine [30] and [40] → [30, 40]
  - Then combine [20, 70] with [30, 40] → [20, 30, 40, 70]
- Continue this process for the right side similar to the left side.
- Final sorted result for the entire array: [10, 20, 30, 40, 50, 60, 70].

The same merge sort can be applied to sort strings/words alphabetically.
Example with the word "question":
- Split into two groups: Left - [q, u, e, s] and Right - [t, i, o, n].
- Continue splitting each group until single letters are reached.
- Merge them back in alphabetical order.
- Final sorted order for "question": [e, i, n, o, q, s, t, u].

General Time Complexity: O(n log n) for all cases (best, average, worst).
Recursive Definition:
- T(n) = 2T(n/2) + n
- This represents the time taken to split and merge the arrays.

Use the Master Theorem:
- T(n) can be expressed as T(n) = 2T(n/2) + n.
- This can be solved to derive the time complexity as:
  - Final Complexity: T(n) = O(n log n)