Merge Sort - A Divide and Conquer Algorithm

Merge Sort is an efficient, stable, and comparison-based sorting algorithm that follows the divide and conquer paradigm. It is particularly useful for large datasets as it has a worst-case time complexity of O(n log n).

---

How Merge Sort Works

Merge Sort follows three main steps:

1. Divide:
   Recursively split the array into two halves until each sub-array contains a single element.
2. Conquer:
   Since arrays of one element are inherently sorted, we now have a collection of sorted sub-arrays.
3. Merge:
   Combine the sorted sub-arrays to form a single sorted array. The merging process involves comparing the smallest elements of each sub-array and arranging them in order.

---

Example Walkthrough

Consider the array: [8, 3, 5, 4, 2, 7, 6, 1]

Step 1: Divide

[8, 3, 5, 4] | [2, 7, 6, 1]

Splitting further: [8, 3] | [5, 4] and [2, 7] | [6, 1]

Step 2: Conquer

Each sub-array with one element is considered sorted: [8] [3] [5] [4] [2] [7] [6] [1]

Step 3: Merge

Merge each pair of sub-arrays in sorted order:

• Merge [8] and [3] → [3, 8]
• Merge [5] and [4] → [4, 5]
• Merge [2] and [7] → [2, 7]
• Merge [6] and [1] → [1, 6]

Now merge these intermediate arrays:

• Merge [3, 8] and [4, 5] → [3, 4, 5, 8]
• Merge [2, 7] and [1, 6] → [1, 2, 6, 7]

Finally, merge [3, 4, 5, 8] and [1, 2, 6, 7] → [1, 2, 3, 4, 5, 6, 7, 8]

Summary

• Merge Sort divides the array into halves, recursively sorts them, and then merges the sorted halves.
• It is highly efficient with a time complexity of O(n log n).