How it works?

Merge Sort follows three steps: divide, conquer, and combine.

Step-by-Step Process:

1. Divide: split the array into two halves.
2. Conquer: recursively sort each half. A piece with one element (or none) is already sorted, so the recursion stops there.
3. Combine: merge the two sorted halves into one sorted array.

Example on [6, 3, 8, 5]:

• Split into [6, 3] and [8, 5]
• Split again: [6], [3], [8], [5]
• Merge [6] and [3] into [3, 6]
• Merge [8] and [5] into [5, 8]
• Merge [3, 6] and [5, 8] into [3, 5, 6, 8]