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. The merge procedure merges the arrays out-of-place using an output array, using the same algorithm we would use while combining two sorted piles of cards: we compare the cards at the top of the input piles, pick the smallest one and place it face down on the table. Removing a card from an input pile uncovers a new card in the respective input pile. We repeat the operation until we deplete one input pile, and then we place the remaining pile face down at the top of the output pile.