Summary

Merge Sort is a classic Divide and Conquer algorithm. Its strategy is to break down a complex problem into smaller, more manageable sub-problems, solve them, and then combine the solutions. For sorting, this means recursively splitting the array into halves until each sub-array contains only one element (which is inherently sorted), and then merging these sorted sub-arrays back together to produce a fully sorted list.

How it Works

• 1. Divide: The algorithm first divides the array into two equal halves. If the array has an odd number of elements, one half will have one more element than the other.

• 2. Conquer (Recurse): It continues to divide each of these halves recursively until it has a collection of sub-arrays, each containing a single element. A single-element array is considered sorted by definition.

• 3. Merge: Starting with the single-element arrays, the algorithm repeatedly merges adjacent pairs of sub-arrays. In each merge operation, it creates a new, sorted array by comparing elements from the two input arrays one by one and picking the smaller one. This step continues until all the sub-arrays have been merged back into a single, fully sorted array.