Merge Sort: Difference between revisions
Jump to navigation
Jump to search
| Line 13: | Line 13: | ||
# '''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, <font color=darkgray>if n is odd ...</font> | # '''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, <font color=darkgray>if n is odd ...</font> | ||
# '''Conquer''': it calls itself recursively to sort the sub-arrays. The recursion "bottoms out" when the sequence to be sorted has length 1. | # '''Conquer''': it calls itself recursively to sort the sub-arrays. The recursion "bottoms out" when the sequence to be sorted has length 1. | ||
# '''Combine''': it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure. | # '''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 it 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. | ||
Revision as of 23:47, 6 August 2018
Internal
Overview
Merge sort is a divide-and-conquer algorithm.
Algorithm
Merge sort works as follows:
- 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 ...
- Conquer: it calls itself recursively to sort the sub-arrays. The recursion "bottoms out" when the sequence to be sorted has length 1.
- 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 it 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.