Talk:Sorting algorithms/Merge sort

Merge Sort can be an iterative sort

The merge sort is NOT a recursive sort through necessity (unlike the quick sort) but through implementation. An alternative algorithm for the merge sort looks like this:

 n=1
 Repeat
   Merge lists of size n
   Double n
 Until n >= Size

This is a purely iterative process. Starfiend 14:20, 24 July 2010 (UTC)

Java implementation

I don't know if you want functions tuned towards efficiency (rather than code readability), but the java implementation accesses a linked list through an index, which a big performance hit in any language. A much faster implementation (50x faster on a list of 100,000 elements) would be to use an iterator:

int i = 0;
for (E d : m)
    if (i++ < middle)
        left.add(d);
    else
        right.add(d);

--Zastrowm 17:34, 6 January 2011 (UTC)

I made the change. It looks just as readable each way I think and since it's such a big performance boost it seems like a good idea. Thanks. --Mwn3d 19:12, 23 January 2012 (UTC)