Merge Sort

Internal

• Data Structures and Algorithms
• Sorting Algorithms

Overview

Merge sort is a divide-and-conquer algorithm.

Algorithm

Merge sort works as follows:

1. Divide: it divides the initial input array into two roughly equal sub-arrays of n/2 elements each. If n is even, the array is equally split, if n is odd ...
2. Conquer: it calls itself recursively to sort the sub-arrays. The recursion "bottoms out" when the sequence to be sorted has length 1.
3. Combine: it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure.