Merge Sort: Difference between revisions
Jump to navigation
Jump to search
Line 8: | Line 8: | ||
Merge sort is a [[Data Structures and Algorithms#Divide_and_Conquer|divide-and-conquer]] algorithm that sorts an input array as follows: | Merge sort is a [[Data Structures and Algorithms#Divide_and_Conquer|divide-and-conquer]] algorithm that sorts an input array as follows: | ||
# '''Divide''': it divides the initial 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 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 | # '''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 | # '''Combine''': it merges the two sorted sub-arrays to produce the sorted answer, by invoking an auxiliary Θ(n) procedure. |
Revision as of 23:29, 6 August 2018
Internal
Overview
Merge sort is a divide-and-conquer algorithm that sorts an input array as follows:
- Divide: it divides the initial 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.