This is where two items are sorted, then another two items. Next, those total four items are ordered. The process continues again until the next four are sorted, then those first eight are then sorted. The pattern continues until everything is sorted.
1. If the input sequence has only one element, return.
2. Partition the input sequence into two halves.
3. Sort the two subsequences using the same algorithm.
4. Merge the two sorted subsequences to form the output sequence.
Here's a Java animation if you need some help visualizing this: http://www2.ics.hawaii.edu/~qizhang/ics665/mergesort.html
last edited (November 2, 2006) by bilderbikkel
Back to the page