There is no merge sort on your webpage.
There is now.
By "2-way merge", do you mean iterating through the 2 partition at the same time, taking the smaller of each list ?
yes, an sequential pass interleave, what a card collating machine used
to do in the olden days.
A mergesort sorts bundles by any of a number of means. Then it merges
the bundles, with very simple copy loop. The code in
http://mindprod.com/products2.html#SORTED is full of merge loops.
You don't use merge sorts for sorting a small number of items.
Normally the only time you use them is for external sorts, where you
sort ram-fulls of data, put them on disk, then read N bundles
simultaneously sequentially and output a combined bundle, gradually
reducing the number of bundles.
This takes me back to the 60s when I wrote a mag tape sort.
Back then much of your logic was about trying to get the final pass to
come out right to land on the desired tape. You used several reels for
scratch. It is much easier with disk, but for a fast sort, each
scratch should be on a different physical drive.
In your case, it is duck simple. Split your data logically in two,
(experiment to see if copying into two separate arrays helps or
hinders). Turn a Sun sort loose on both halves. Wait until both
threads are done. Merge the two outputs into one, and return that
array, or copy it back into the original with System.arraycopy.
If you write a sort for a List, e.g. ArrayList, with proper generics,
it will work on collections of any type that supports Comparable or
Comparator. To see how to pull it off, have a look at the source for
any of my sorts, or Sun’s sort.
However, because of Java’s lack of orthogonality, your List sort won’t
work for arrays of such Objects. You need to write very similar code
to do that. Even that array version won’t sort an array of primitives
such as long, int or byte. You have to write yet another slightly
different version of the sort to handle each type of primitive.
