Merge Sort

Merge sort is a recursive sort that uses a strategy called divide and conquer.

Instead of sorting the entire array at once, merge sort uses recursion to repeatedly divides the array into smaller halves until each subarray contains only one element. Since a single element is already sorted, the algorithm then merges the smaller arrays back together in sorted order.

For example, consider the following array.

Merge sort divides the array into smaller pieces.

After the array has been divided into individual elements, merge sort combines them back together while keeping each merged group sorted.

Because merge sort repeatedly divides the problem into smaller pieces, it performs efficiently even for very large collections of data.