What is Merge Sort?

Merge Sort is a Divide and Conquer algorithm.

Idea:

1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves

Key thought:

“Break the problem until it’s trivial, then combine the answers.”

Step-by-Step Example

Given array

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide

[38, 27, 43, 3]   [9, 82, 10]

Divide again:

[38, 27] [43, 3]   [9, 82] [10]

Divide until single elements:

[38] [27] [43] [3] [9] [82] [10]