Java Reference
In-Depth Information
Suppose we have an array of 10 integers. Let us engage in a bit of wishful thinking
and hope that the first half of the array is already perfectly sorted, and the second half
is too, like this:
Now it is simple to merge the two sorted arrays into one sorted array, by taking a new
element from either the first or the second subarray, and choosing the smaller of the
elements each time:
In fact, you probably performed this merging before when you and a friend had to
sort a pile of papers. You and the friend split the pile in half, each of you sorted your
half, and then you merged the results together.
The merge sort algorithm sorts an array by cutting the array in half, recursively
sorting each half, and then merging the sorted halves.
639
640
That is all well and good, but it doesn't seem to solve the problem for the computer. It
still must sort the first and second halves of the array, because it can't very well ask a
few buddies to pitch in. As it turns out, though, if the computer keeps dividing the
array into smaller and smaller subarrays, sorting each half and merging them back
together, it carries out dramatically fewer steps than the selection sort requires.
Search WWH ::




Custom Search