Merge Sort: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
Merge sort works as follows: | 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 | # '''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 split in two equal halves, if n is odd, the right array is bigger than the left array with one element. This is where we test whether the recurrence bottoms out: if the middle of the array and the left edge coincide, we have one-element array and it is time to stop the recurrence. | ||
# '''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. The merge procedure merges the arrays in-place, using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, 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. | # '''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 in-place, using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, 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. | ||
Revision as of 00:58, 7 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 split in two equal halves, if n is odd, the right array is bigger than the left array with one element. This is where we test whether the recurrence bottoms out: if the middle of the array and the left edge coincide, we have one-element array and it is time to stop the recurrence.
- 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 in-place, using the same algorithm we would use while combining two sorted piles of cards: we use two sorted input piles, 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.