Talk:Merge sort
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions. | |
| ??? | This article has not yet received a rating on the assessment scale. | |
| ??? | This article has not yet received an importance rating on the assessment scale. | |
[edit] sort
On a boring weekend, I sat down with my computer trying to implement some sorting algorithms. Then I started working on a Mergesort implementation. I didn't have internet access, so all the help I had was foggy memories of this page. Everything went fine until I started working on the merge function (I was programming in Java, BTW). I tried to make a merge function that could merge the two ranges without using a temporary array, something like the above merge function in C, but without the v1 and v2 arrays. (I thought that I had seen such a method on this page - came back tonight and saw that I hadn't ;-)
I had limited success in making the function work - is it at all possible?
- moved from article page -- John Owens 20:48 Apr 21, 2003 (UTC)
- # (cur) (last) . . 15:33 Apr 21, 2003 . . 217.209.32.132 (The tale of Joe Random Hacker trying to make a merge function without using temporary arrays)
[edit] Replacing the C sample code
I think the current C sample code isn't very useful. The purpose of sample code on an algorithm page has to be to convey how the algorithm works, in a concise and readable manner. The point is not to provide an efficient implementation that users can copy&paste.
I propose replacing the lengthy C sample by the following Python code:
def merge(a, b): # Merging is trivial if one list is empty. if len(a) == 0: return b if len(b) == 0: return a # Merge non-empty lists by taking the smaller one of the two # head elements, and recursively merging the remaining lists. if a[0] <= b[0]: return a[0:1] + merge(a[1:], b) else: return b[0:1] + merge(a, b[1:]) def mergesort(a): # Lists of 0 or 1 elements are already sorted. if len(a) <= 1: return a # Split list in half, sort halves separately and merge. m = len(a) // 2 # // is integer division return merge(mergesort(a[0:m]), mergesort(a[m:]))
I think Python is a good choice here because
- the syntax is uncluttered and fairly easy to read, even if one isn't familiar with the details of Python
- array slice and append operations make for a much more concise formulation of the algorithm, where the C code has to shuffle around single elements in loops.
- While the algorithm could probably be expressed even more elegantly in a functional language ike Scheme, I think an imperative formulation will be easier to understand for the majority of readers.
If there are no objections, I will go ahead and make the changes. --K. Sperling 12:45, 17 Jul 2004 (UTC)
The definition given in this article is for a Binary merge sort. Higher orders of merge are possible (e.g. Ternary merge sort, divide unordered list into three lists of approximately equal size, sort those, then merge the three ordered lists). Well-written Mergesort and Heapsort implementations have approximately the same performance (if anything Mergesort usually wins by a whisker).
wait a moment... This code is erraneous!!!
I tested the mergesort code in float and int variations in C. The combinations of Sort and Merge functions here on Wikipedia don't work in a simple C compiler. After compilation the results of a run are sorted in the wrong order!
-- Glenn.L.Williams@nasa.gov This paragraph is the opinion of the author only and not that of NASA!!!
[edit] MIPS? Miranda?
I removed the MIPS assembly version of the code, because this isn't the 99 Bottles of Beer page, and I don't think anybody is going to be enlightened about how the algorithm works by pages of assembly code.
I also suggest that the Miranda example should be removed. It's almost the same as the Haskell one - it seems to differ only in the syntax for taking the left half and right half of a list - and Haskell is more well known than Miranda, at least based on the one data point that I've never heard of Miranda.
RSpeer 17:29, Apr 21, 2005 (UTC)
[edit] Analysis of moves is suspect
The assertion that quicksort's best case behavior is N log N moves must depend on some very specific implementation. If the element in the middle is used as the pivot (not a good idea, but often seen), then input that is already in order will result in 0 moves. I'd favor removing the discussion of best case behavior.
I'm also suspicious about the assertion that merge sort does better on average than quicksort on moves. Merge sort will move all the elements, log N times. On average, quicksort will find half the elements on the proper side of the pivot, so it should only have to move 1/2 the elements, log N times.
Algorithmic analysis is not my field, so I won't attempt to edit the article. But it would be nice to have an expert check out the validity of the analysis. —The preceding unsigned comment was added by Jpl (talk • contribs) .
- It's not talking about the number of moves; it's talking about the number of steps the algorithm has to take. Even if quicksort doesn't actually do any swaps, it still has to inspect elements in the list; and it's been proven that any comparison-based sorting algorithm must take at least O(N log N) time.
- With respect to your statement "it should only have to move 1/2 the elements, log N times", well, this is O-notation we're talking about, so that's actually equivalent to saying O(N log N), since N/2 log(N) is also O(N log N). --Saforrest 04:26, 11 April 2006 (UTC)
- The main page says In terms of moves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case. We've already established that the best case number of compares is O(N log N), so of course the number of steps can be no better than O(N log N). I don't think we're in disagreement about the behavior, but the article asserts that quicksort best case moves is O(N log N), and that's simply false (and largely irrelevant). --jpl 22 June 2006
Quicksort can indeed fall in the θ(n2) in its worst running cases, but it is generally expected to behave θ(n lg n). Also randomizing the algorithm (pivot selection) largely decrease the likelyhood of a worst case. The reason why it is regarded as one of the fastest algorithm is the low hidden constants hidden in the average θ(n lg n)[1]. I would also remove this discussion from the main page, given the lack of sources agreeing with this section's author opinion. --TheSpooler 02:58, 26 June 2007 (UTC)
[edit] References
- ^ Introduction to Algorithms, Cormen Leiserson and Rivest, McGraw Hill, 1990, p.153
[edit] Question about the C implementation
I have one question... Imagine you have one array of integers, {40, 3} for instance. Using the current implementation of mergesort, begin == end -1 so the function returns. However, the array is not sorted. Or did I missunderstand anything? Thank you!
- In C, conventionally (and also in this case), end pointers point past the end of the sequence, so begin == end signifies an empty seqence. --K. Sperling June 30, 2005 22:25 (UTC)
[edit] What about bottom-up merging?
It ain't necessarily true that Mergesort requires more recursive method calls than Quicksort. If Mergesort and Quicksort are delegating to another sort routine (e.g. Insertion Sort) for small subarrays, then comparing the number of recursive method calls is pointless. If Mergesort is implemented bottom-up (as per Knuth, "Art Of Programming", volume 3, 2nd Edition, Natural and Straight Merge algorithms) rather than top-down there need be *NO* recursive method calls at all. Recursive call overhead is "small change" when N is large anyway: it contributes at most an O(N) component to average running time.
The bottom-up merge formulation is typically something like this:
1. divide the array into subarrays of size M (the last subarray may be <M elements); sort each such subarray
2. merge the first two subarrays of size M, then the next two, and so on
(if there is an odd number of subarrays, leave the last one untouched)
(if there is an even number of subarrays, the last one may contain less than M elements)
3. set M = M * 2
4. if M<N, go back to step 2
I would not be at all surprised to find that the Mergesort Von Neumann proposed (way back in 1945) was bottom-up rather than top-down. The recursive top-down mergesorts (that are now so much more popular) were probably invented somewhat later.
Quicksort's real advantage over Mergesort (in terms of average running time) comes down to the amount of record movement. Quicksort typically requires a shade below half the record movement of (Binary) Mergesort (the ratio depends on how the Quicksort pivot values are selected).
Re: the article's assertion that Mergesort's best case only "takes about half as much time" as the worst case. That depends. For typical mergesort implementations the best case requires half as many comparisons but just as many record moves. For some implementations (e.g. Natural Merge - see Knuth) only O(N) comparisons and O(N) moves are required for the best case (such implementations tend to have a longer *average* running time, however).
-James Barbetti (08-Jul-2005)
[edit] Natural Mergesort
This type of merge sort I read about first in 'Scheme and the Art of Programming', George Springer and Daniel P. Friedman.
They call it a natural mergesort.
Here is a first stab (in python) at a bottom up , inplace merge sort:
def count_sorted( items, start=0 ):
for x in range(start+1,len(items)):
if items[x-1]>items[x]:
return x - start ;
return len(items) - start ;
def reinsert( items, val, start, end ):
for x in range( start, end-1 ):
if items[x+1] > val :
items[x] = val
return
else:
items[x] = items[x+1]
items[end-1] = val
def merge_sublists( items, left, right ):
for x in range(0,left):
if items[x] > items[left]:
val = items[x]
items[x] = items[left]
reinsert( items, val, left, left+right )
def merge( items ):
left= count_sorted(items)
while left < len(items):
right = count_sorted( items, left )
merge_sublists( items, left, right )
left = left + right
A possible optimization is that when the longest ordered sublist is one, find the longest reverse ordered list and reverse it.
-David Medlock, Jan 13, 2006
[edit] minor edit to Optimizing
Comparing RAM to a tape drive is a bit of a stretch, but if "in some sense" means sequential access only, it's not too far-fetched. Still, even if RAM is the slowest of the various memory cache levels, it is much, much faster than a tape. A naive reader might have interpreted the original text to mean that RAM is comparable in speed to a slow tape drive. So I changed "slow" to "fast" (which still preserves the relative speeds of the various caches mentioned, but also preserves the speed relative to tape drives).
---
Perhaps it would be worth mentioning when this matters. These issues are only relevant with large sets of elements. In particular, I believe databases (e.g. SQL and whatnot) tend to use mergesort.
[edit] Could use a Lisp example
I think a Lisp example of the code for merge sort would be illuminating. Due to the nature of Lisp this variation of merge sort is going to have to be bottom-up rather than top-down (to preserve O(nlogn) efficiency, anyway). I'm working on figuring it out but in the mean time if someone else already knows it that'd be great too. --Cyde 05:22, 11 November 2005 (UTC)
- I don't think we need more example code, in fact I think we already have way too much. These example code sections seem to be used more as advertisements for everybody's respective favorite language. For example the Ruby and Python samples differ in nothing but syntax details. The Haskell and Miranda ones are also practically identical. I'd actually like to remove the samples completely or at least move them into a separate article or onto wikisource. The question to ask is, are the samples illustrating the algorithm, or are they just there to illustrate how elegant and superior language X is? It seems to me that it's mostly the latter.
- And don't get me wrong, I'm not accusing you of lobbying for Lisp. Just the fact that you mentioned adding more samples reminded me that I'd wanted to say something on that subject for some time now :-)
- And a section on the bottom-up version of merge sort WOULD be very good to have. --K. Sperling (talk) 01:00, 12 November 2005 (UTC)
-
- This happens on every sorting algorithm page. My approach has been to break these out into a separate article, just keeping a few of the most illustrative ones in the original. See quicksort implementations and insertion sort implementations. Deco 03:09, 21 November 2005 (UTC)
The Common Lisp code in the article is rather slow and isn't really mergesort as understood in the article as a whole. Something like this is a lot faster (comparable to the built in sort function in the implementation I use (I don't know which algorithm(s) it uses)) and really is mergesort:
(defun merge-sort (list &optional (fn #'<)) ;Common Lisp mergesort
(labels ((msort (list)
(if (null (cdr list)) list
(let ((splitpoint (ceiling (/ (length list) 2))))
(merge (msort (subseq list 0 splitpoint))
(msort (nthcdr splitpoint list))))))
(merge (list1 list2)
(cond ((null list1) list2)
((null list2) list1)
(t (let ((car1 (car list1))
(car2 (car list2)))
(if (funcall fn car1 car2) (cons car1
(merge (cdr list1)
list2))
(cons car2
(merge list1
(cdr list2)))))))))
(if (null list) nil
(msort list))))
Maslin 02:12, 31 July 2007 (UTC)
- Well, looks like the language wars are starting all over again. Based on the previous discussions, it seems that the Lisp example should simply be deleted, particularly since it's wrong. (It had only been here a few days before Maslin's comment above.) So, I'm deleting it. Personally, I lean to the view that it's nice to have an example implementation in functional style as well as one in imperative style, and would be inclined to include a Python version even though I'm personally fonder of Lisp. I see the C++ code has been here only since mid-May; but I leave that for someone to delete who participated in the earlier decision not to include implementations. ScottBurson 06:26, 2 September 2007 (UTC)
[edit] Removal of implementations
I intend to remove the implementations from this page if Wikipedia:Articles for deletion/Selection sort implementations is successful. They will be transwikied to the existing implementation page at WikiSource. —donhalcon╤ 06:00, 5 March 2006 (UTC)
- Already done :) —Ruud 23:19, 5 March 2006 (UTC)
[edit] C code
I have a working implementation in C. Not optimizations done to make it clear what is happening...
/* Inital call to mergeSort should be arraysize - 1 */
void mergeSort(int a[], int low, int high)
{
int length, mid;
int *temp1, *temp2;
int tmp_pos1, tmp_pos2;
int i;
/* Array is 1 element and sorted so return */
if (low == high)
return;
/* Divide the array in half and sort */
length = high - low + 1;
mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid+1, high);
/* Put half the array in 1 temp array */
temp1 = malloc(sizeof(int)*(mid-low+1));
temp2 = malloc(sizeof(int)*(high-mid));
i = low;
for (tmp_pos1 = 0; tmp_pos1 < (mid-low+1); tmp_pos1++)
{
temp1[tmp_pos1] = a[i];
i++;
}
/* and the other half in other temp array */
i = mid+1;
for (tmp_pos2 = 0; tmp_pos2 < (high-mid); tmp_pos2++)
{
temp2[tmp_pos2] = a[i];
i++;
}
/* Merge the two temp array back into the original array */
tmp_pos1 = 0;
tmp_pos2 = 0;
i = low;
while ((tmp_pos1 < (mid-low+1)) && (tmp_pos2 < (high-mid)))
{
if (temp1[tmp_pos1] < temp2[tmp_pos2])
{
a[i] = temp1[tmp_pos1];
tmp_pos1++;
i++;
} else {
a[i] = temp2[tmp_pos2];
tmp_pos2++;
i++;
}
}
/* At this point, we've completely merge one of the arrays
back into the original array. Now, just tack on the
remaining elements of the other temp array */
while (tmp_pos1 < (mid-low+1)) {
a[i] = temp1[tmp_pos1];
tmp_pos1++;
i++;
}
while (tmp_pos2 < (high-mid)) {
a[i] = temp2[tmp_pos2];
tmp_pos2++;
i++;
}
free(temp1);
free(temp2);
}
[edit] More C examples
Here is a shorter C example, first a simple version and then an optimised version of the same code. The code is written from scratch, and has no licence.
void mergesort(unsigned int n, int *input, int *scratch)
{
if(n<=1)
return;
{
unsigned int i = 0;
unsigned int mid = n/2;
int* left = input;
int* right = &input[mid];
int* endr = &input[n];
int* endl = right;
/* Sort sub arrays */
mergesort(mid, left, scratch);
mergesort(n-mid, right, scratch);
/* Merge sorted sub arrays */
for(i=0; i<n; i++){
if(left < endl && (*left<*right || right>=endr))
scratch[i] = *left++;
else
scratch[i] = *right++;
}
for(i=0; i<n; i++)
input[i] = scratch[i];
}
}
void mergesort_opt(unsigned int n, int *x, int *s)
{
if(n<=1)
return;
{
unsigned int i = 0;
unsigned int mid = n/2;
int* left = s;
int* right = &s[mid];
int* endr = &s[n];
int* endl = right;
/* Sort sub arrays */
mergesort(mid, x, left);
mergesort(n-mid, &x[mid], right);
/* Merge sorted sub arrays */
while(1){
if(left >= endl || right>=endr)
break;
if(*left < *right)
*x++ = *left++;
else
*x++ = *right++;
}
/* Copy tails */
if(left<endl)
memcpy(x,left,sizeof(int)*(endl-left));
else
memcpy(x,right,sizeof(int)*(endr-right));
}
}
/* Example of how to call the sort algorithm */
#define N 9
int main(void)
{
int i;
int x[N] = {-7, 6, 5, 6, 8, 4, 4, -12, 0}; /* Input vector */
int s[N]; /* Scratch space */
/* Display input */
for(i=0;i<N;i++)
printf("%d ",x[i]);
printf("\n");
/* Call sort algorithm */
mergesort_opt(N, x, s);
/* Display result */
for(i=0;i<N;i++)
printf("%d ",x[i]);
printf("\n");
return 0;
}
[edit] Two-Phase, Multiway Merge-Sort (TPMMS)
This is a variation of merge sort that can be implemented when the data to be sorted does not fit into memory and sorted subarrays have to be temporarily stored on disk. Someone may want to expand on that and put it on the main page. —The preceding unsigned comment was added by 65.111.84.3 (talk) 18:04, 1 March 2007 (UTC).
Agreed Stephenbez 03:54, 10 April 2007 (UTC)
[edit] Which is faster?
It might be that I am not so good at English, but I don't understand from the section "Comparison with other sort algorithms" which algoritm is actually faster? It says "Quicksort, however, is considered by many to be the fastest general-purpose sort algorithm although there are proofs to show that merge sort is indeed the fastest sorting algorithm out of the three. Its average-case complexity is O(n log n), even with perfect input and given optimal pivots quick sort is not as fast as merge sort and it is quadratic in the worst case. On the plus side, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media."
I find this confusing. In the comparisments I have made, Quicksort outperforms Merge sort. What does the section say? / Fred-Chess 14:19, 11 April 2007 (UTC)
A heavily tuned quick sort, such as the one in C++'s std sort function, will on average outperform merge sort. See: http://warp.povusers.org/SortComparison/ and http://linux.wku.edu/~lamonml/algor/sort/sort.html --129.97.240.61 15:49, 17 April 2007 (UTC)
I think the source of the debate over which is faster between Quicksort and Merge Sort is the fact that Quicksort's worst-case complexity is O(n²), which is worse than Merge Sort's worst- (and indeed, best-) case complexity of O(n log n). This means that, for some sequences, Quicksort behaves very badly compared to Merge Sort. How commonly the worst case is encountered depends heavily on the choice of pivot in Quicksort; some choices, for example, will yield worst-case performance when the input sequence is already sorted, or is sorted in reverse. Even in Quicksort's much-touted average case it doesn't beat Merge Sort asymptotically. However, a well-crafted Quicksort implementation can minimize its worst cases by clever choice of pivot, and will be several times faster than Merge Sort for most input. --75.6.33.163 00:37, 21 April 2007 (UTC)
RE: Mergesort vs Quicksort ... When Quicksort is well implemented it will run faster on a Modern desktop than Mergesort because of the processor's cache. The overhead of swapping to and from System Memory is costly, and this is not something that a programmer can write around. Also, each step of a recursive Mergesort implemented in an OO language has overhead of object creation. Quicksort will rarely have a n² behaviour unless someone creates a sequence of numbers that is intended to force Quicksort "Quadratic", this is sometimes done intentionally to cause a Denial of Service Attack.Asturneresquire 09:43, 2 August 2007 (UTC)
I think the statement "although there are proofs to show that merge sort is indeed the fastest sorting algorithm out of the three" is completely made up. It's not clear how "speed" is being measured (number of exchanges? number of cache misses? what about allocation overhead?), it's obviously denied by the fact that quicksort outperforms mergesort in practice on many real lists, and it gives an impression of authority with no source to back it up. If you believe this, I have a wonderful proof of P=NP that is too small to fit in the margin of this talk page. Dcoetzee 20:19, 2 August 2007 (UTC)
[edit] Proper merge sort is bottom up + which is faster?
Proper merge sort is bottom up
A proper merge sort is bottom up. There are two phases. The first is a "make groups" pass which creates groups of sorted records. In the simplest case, each record can be considered to be a group of size 1. The next simplest case is to compare pairs of records and swap those that are not in order to create groups of size 2. If there is a resonably significant amount of pre-ordered data, then it speeds up a merge by quite a bit to make groups of ascending or descending sequences records, called a variable group or "natural" merge sort. In the case of descending records, the records are normally reversed in the "make groups" pass, but could be dealt with in the first merge pass. The next phase of a merge sort is to merge the groups created by "make groups", using the normal bottom up merge algorithms already mentioned here.
Tape Sort
For a tape sort, unlike what the article mentions, the first pass is a "make groups" pass. The amount of memory available for sorting records determines the initial group size, and these groups are written alternately to the two "output" tape drives. For minimal housekeeping with a tape sort, group sizes don't have to be kept. Single file marks can be used to indicate the end of a group, and double file marks used to indicate the end of data.
Which is faster?
Microsoft's sort() [a quicksort] is about 15% faster than Microsoft's stable_sort() [a bottom up merge sort] on truly random data, and when not using a user supplied compare routine. If using a user supplied compare, or if the data has significant ordering, then a merge sort I wrote is faster, 29% when using a user supplied compare routine, and the natural merge sort is faster still if there is significant ordering of data. Otherwise my merge sort is about the same as the Microsoft stable_sort(). Note that the Microsoft sort() does not maintain record order on "equal" records, if this is important, then use stable_sort() instead.
If using external disk storage, then a merge sort is the fastest because it's sequential nature allows very large numbers of records to be read or written per random access on a disk (at least 1/4 of memory available for record storage during the sort).
The best case for a "natural" merge sort (one that makes groups from ascending or descending record sequences) is O(n-1) on a pre-ordered file (all ascending). During "make groups", n-1 compares are done, resulting in a single group and "merge groups" does nothing. If all descending, then a single reverse records pass is done, which could be done while writing the results to a file.
I compared Microsoft's standard template library sort() program with their stable_sort() program plus a merge sort of my own. First note that these are not library functions but instead are actual code in the include file <algorithm>, and are compiled along with the callers code for the specifics of the vector template being used, such as element size, number of elements (unless push_back is used repeatedly) and whether or not a user function is used for the compare. There is seperate code for the non user supplied compare versions and the user supplied compare versions, and the user supplied compare versions are significantly slower.
I didn't investigate the Microsoft sort(). The stable_sort()'s "make groups" uses insertion sort to create groups of 32 elements then goes into it's "merge sort" phase, using a second allocated temporary vector. Each pass merges to and then from the temporary vector. My fixed size merge sort just creates groups of 1 or 2 records, and my "natural" merge sort scans for ascending and descending sequences to create groups, the smallest size being 2 (except for last record on a odd number of record file).
Personal history
I've written several merge sorts, my first one dating back to 1974.
Jeffareid 07:10, 18 September 2007 (UTC)
[edit] int middle = (left + right) / 2;
I don’t think the “Typical implementation bugs” section belongs in the article. The error described there is quite common; if it deserves to be mentioned in an article, it should be something like Binary search algorithm. Besides, the section’s suggestions are incorrect. First of all, in C and C++, where truly one has no “>>>” operator, the proposed code is undefined behaviour anyway as it tries to convert the result of a signed integer overflow to unsigned. Secondly, first + (last - first) / 2 is the only true way to compute the middle of a range, because, for instance, it is the only expression that works for pointers/iterators. Roman V. Odaisky 21:06, 19 October 2007 (UTC)
- Smart compilers will turn / 2 into a SAR -- no need for an extra >>> operator. [ -j.engelh (talk) 15:07, 22 November 2007 (UTC) ]
[edit] Java Arrays.sort() using merge sort?
The current text says:
- In Java, the Arrays.sort() methods use mergesort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.
This sounds incorrect. All sort(...) methods in the Arrays class take arrays as inputs (Java 1.5), which means that it cannot switch algorithms based on the underlying data types.
But java.util.Collections.sort() does use a modified mergesort [1]
-- nyenyec ☎ 21:05, 11 November 2007 (UTC)
This is in fact correct. I added citations. 207.196.180.201 (talk) 05:14, 20 November 2007 (UTC)
[edit] In place and stable is not possible
I'll comment here because I'm not familiar with Wikipedia. Jyrki Katajainen, the 3rd reference, provides a way to gain in-place sorting by sacrificing stability. If you read his article, it's clear he scrambles the first half/third of any sequence as he uses that as work space. I doubt in-place stable is possible, but even if it were, Jyrki Katajainen does not demonstrate how to do it. There's also a table comparing algorithms which states in-place merge sort is stable. Again, Jyrki Katajainen does not support this, I doubt this is possible.
In comments at the end of his work Jyrki Katajainen notes that in-place stable is an open problem.
Shafarevich (talk) 13:58, 18 April 2008 (UTC)
- This is a great catch and really ought to be fixed. Dcoetzee 21:12, 18 April 2008 (UTC)
Apparently, they solved this problem by the end of 1995. See:
- Viliam Geffert, Jyrki Katajainen, Tomi Pasanen; "Asymptotically efficient in-place merging"
- Jingchao Chen; "Optimizing stable in-place merging"
- Antonios Symvonis; "Optimal Stable Merging"
- Pok-Son Kim, Arne Kutzner; "On Optimal and Efficient in Place Merging"
- Bing-Chao Huang, Michael Langston; "Fast Stable Merging and Sorting in Constant Extra Space"
Though, programming it looks like a different kettle of fish ;) --Como (talk) 07:38, 28 April 2008 (UTC)
By the way... http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html --Como (talk) 09:41, 28 April 2008 (UTC)
[edit] Animation Needed
(Refactored from the top of the page.) How about we use a slightly different picture, one that shows the elements of the array moving(the arrow pointing to) into the correct position. —Preceding unsigned comment added by 75.140.235.49 (talk) 14:10, 11 March 2008 (UTC)
I believe some animation will help people understand it better.Just like the GIF animation in Quicksort algorithm. Can someome make one? Thanks in advance!Visame (talk) 18:44, 3 May 2008 (UTC)
- There is an animation in the Analysis section. I suspect that the mergesort, however, is not very elegantly animate-able. So, this is the best that is likely to be given, unless someone wants to contribute something better. silly rabbit (talk) 19:12, 3 May 2008 (UTC)
[edit] merge() function pseudocode problem
I'm not sure, if the merge() function pseudocode is right.
If the execution came to the line
if length(left) > 0
it means that the list right is empty and the whole list left can be appended to the list result. But if we append just a tail of the list left (as it actually done in the next line of the pseudocode), one element will be lost.
Analogous problem is with the lines
if length(right) > 0
append rest(right) to result
I believe this part of pseudocode should look like this:
if length(left) > 0
append left to result
if length(right) > 0
append right to result
i.e. without applying rest() on the left and right lists. —Preceding unsigned comment added by 217.95.54.23 (talk) 13:40, 28 May 2008 (UTC)
