Talk:Sorting algorithms/Merge sort: Difference between revisions
Content added Content deleted
(Created page with '== 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 f…') |
|||
| Line 10: | Line 10: | ||
This is a purely iterative process. |
This is a purely iterative process. |
||
[[User:Starfiend|Starfiend]] 14:20, 24 July 2010 (UTC) |
[[User:Starfiend|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); |
|||
--[[User:Zastrowm|Zastrowm]] 17:34, 6 January 2011 (UTC) |
|||
Revision as of 17:34, 6 January 2011
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)