This is the
talk page for discussing improvements to the
Merge sort article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1 |
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
This
level-5 vital article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
The article mentions a running time of for in-place merge sort, which is wrong. It should be . — Preceding unsigned comment added by Dhruvbird ( talk • contribs) 04:40, 16 March 2015 (UTC)
Two sorted arrays can be merged in place in O(n) time, using O(1) space (temporary variable to swap two elements). To implement mergesort, this merge needs to be repeated log(n) times. You can easily implement mergesort bottom-up stably and in-place. Start with n=1, and merge the slices from i*n to i*(n+1) for i=0 until you exhaust the array. For n=1 this sorts pairs of elements. Then multiply n by 2 and restart until n >= size of the array. — Preceding unsigned comment added by 87.198.115.102 ( talk) 07:53, 26 June 2013 (UTC)
I would second the first posters observation. Its nothing more than an afternoon's coding to get the solution. Think about how it works for a linked list and I you'll get inference for static data, just as the first poster observed. Merge sorts are not in a category of algorithms considered hard to implement, even when they are hybrid. — Preceding unsigned comment added by 80.254.148.163 ( talk) 17:44, 13 June 2014 (UTC)
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
This is Theta(n^2) with Theta(n) merges and Theta(n) complexity in reinsert. 188.120.84.157 ( talk) 04:42, 26 April 2014 (UTC)
It is claimed that the algorithm was invented by von Neumann in 1945. However the reference is to the Knuth book from 1998 (not the first edition, by the way!!!). The reference to an original work performed by von Neumann and published in 1945 is necessary. If the algorithm presented is described only in the Knuth book from 1998, it's from 1998, not from 1945! Riemann'sZeta ( talk) 20:11, 12 April 2011 (UTC)
As an algorithm that can be done recursively and non-recusively, it seems to me that added an example of a non-recursive merge sort algorithm might make this article more complete. I myself am not particularly apt at writing clear and understandable pseudocode, but I feel an example hear would be a good idea. OceanicMeerkat ( talk) 05:52, 27 January 2014 (UTC)
Just try to write that for the real computer. One of the obvious errors is that it splits [0, mid], [mid + 1, high] but then merges [0, mid - 1], [mid, high] — Preceding unsigned comment added by 86.57.194.198 ( talk) 06:28, 18 March 2014 (UTC)
Conceptually if you divide anything into two halves around a (truncated integer) midpoint then the first half will be "begin" to "midpoint", the second half will be "midpoint + 1" to "end". For example, begin = 0, end = 1, midpoint is 0, "left half" is 0, "right half" is 1. With the current code "left half" would be 0, "right half" would be 0 and 1, i.e. the entire list.
In Cracking the Coding Interview, p.118, which uses very similar code to the WP example, the first half is "begin to midpoint", the second half is "midpoint + 1 to end", as I would expect.
I changed right half to midpoint + 1, but my change was reverted by
User:Glrx with the comment "inclusive/exclusive indices". Later in the WP code there is a comment: "https:// left half is A[iBegin :iMiddle-1] // right half is A[iMiddle:iEnd-1 ]." But I don't think that works with truncated integers; in my example of a two element list, left half would be from 0 to -1, i.e. you've walked off the array. It would work with integers which round up, but that's not the case with C style languages, which appears to be the style the code is written in.
Also, even if we were rounding up, the comment implies that the midpoint is only in the right half, whereas with the code as written, it's actually in both halves. Can anyone enlighten me what's going on here? --
Merlinme (
talk)
20:32, 8 December 2014 (UTC)
This is a new article section. It's the primary method used to sort linked lists so it should be included in the article. Implementations of C++ STL (standard template library) function std::list::sort()use this algorithm. Rcgldr ( talk) 00:37, 23 November 2015 (UTC)
Anyone else think the animation example has extraneous comparisons once one of the sides (the left side in all cases) runs out of cells? I thought the point of the whole algorithm is to take advantage of the fact that the partitions being merged are sorted. — Preceding unsigned comment added by 88.192.22.239 ( talk) 14:56, 14 April 2016 (UTC)
Also - the animation appears to be wrong. It does not follow the Top-Down example code because it keeps going back to other, parallel arrays and working on them INSTEAD OF fully sorting the left subarray AND ONLY THEN going back and sorting the right subarray. — Preceding unsigned comment added by 73.157.112.58 ( talk) 02:14, 18 December 2021 (UTC)
The article is completely obscure to those of us who can't read computer code. You break down the list into sub-lists, then you merge them - but how does that work? How do you merge two sorted lists into one? The article just assumes that's easy, as far as the text is concerned. The diagram also shows lists simply being merged and emerging as sorted, without explanation of the merge process. Cyclopaedic ( talk) 09:07, 2 August 2016 (UTC)
I've reverted the midpoint formula back to the clearer (a+b)/2
. The a+(b-a)/2
form is not obvious to most people.
WP should be describing algorithms. In a pseuodcode implementation, the widths of the numbers are not specified because the operations are abstract. The calculations are presumed to not overflow.
Also, the URL https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html is a blog. It is not a reliable source.
At Binary search algorithm#Implementation issues, a big point is made of the Java library bug, but that claim is disingenuous. There's a reason the bug was not discovered for years: it would only occur if somebody did something impractical. It would only be serious issue when one uses 32-bit indices in a 64-bit address space. But indices in 64-bit address spaces should be 64-bit numbers. In a 64-address space, I might want to make an array of more than 232 records; I should be able to use binary search on that array. If the system is only allowing 32-bit indices, then I have bigger problems.
Now the meat.
The numbers used in the algorithm are indices rather than byte pointers. In rational cases, the size of a record will be at least 4 bytes. So in the 32-bit address space case, the record indices will be 30-bit numbers. Overflow will not be an issue. Same for the 64-bit address space.
The Java bug manufactured an irrational case: it made an array of 1.1 billion single bytes and tried to search that array; the numbers overflowed and generated an array-out-of-bounds reference. Think about that array of bytes for a minute. A binary search of an array with 1.1 billion items that can only have 256 distinct items?
WP should not be emphasizing such didactic corner cases. Glrx ( talk) 20:02, 10 October 2017 (UTC)
This section includes the statements: "... producing an in-place merge algorithm that can be combined with a standard (top-down or bottom-up) merge sort ... " "the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage", but logarithmic stack space is only used by top down merge sort, not by bottom up merge sort. Rcgldr ( talk) 16:43, 9 December 2017 (UTC)
Hoping I'm not missing something here, but after going through it many times I think there's something missing in the Top-Down example as of the May 24 2018 edit.
If you do the sort with an array of size 16, then the resulting sorted array ends up in the original array (the one that was "A" in TopDownMergeSort at the top).
...but if you do the sort with an array of size 8, then the resulting sorted array ends up in the work array (the one thas was "B" in TopDownMergeSort at the top).
There is no piece at the end that figures out if the result lies on the wrong array, and copies it over if that's the case.
Jlkeegan ( talk) 03:57, 15 June 2018 (UTC)
A
and B
swap on each level of recursion, as TopDownSplitMerge(B[], iBegin, iEnd, A[])
invokes itself with TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
A
means a source array for split and a destination array for merge at the current level of recursion which can be either the same as the destination array of the whole processing or the working (temporary) copy of source data made at the beginning. And similary (but opposite) for B
, which is a temporary source array for merging at the current level of recursion. Whether it is this or that way depends on whether it is even or odd level of recursion. --
CiaPan (
talk)
08:51, 15 June 2018 (UTC)TopDownSplitMerge
passes its A[]
argument as the last parameter to TopDownMerge
. As a result, the very last merge puts the merged data to the original destination array. Which is correct. It doesn't matter how long the array is – whether it contains two, three, eight, sixteen or a million items – and how many levels of recursion are involved, the final merge always puts data into the correct array. --
CiaPan (
talk)
10:43, 18 June 2018 (UTC)@ CiaPan: Copied from my talk page:
Hi, you have removed File:Merge sort animation2.gif here: Special:Diff/887750333.
Why do you think it's not a mergesort depiction? --CiaPan (talk) 3:10 am, Today (UTC−4)
(I removed it in one other place; not sure why I didn't give as detailed an explanation here). My issue is that it doesn't show the actual merging of sublists, which instead appears to happen instantaneously. In contrast, the animation in the infobox does show the merging. – Deacon Vorbis ( carbon • videos) 12:22, 15 March 2019 (UTC)
The deleted animation is showing the merge sort of an array of random integers. The caption before I changed it didn't indicate at all what was being sorted. The deleted animation is actually more realistic than the other one in this article. In an actual merge sort, the array to be sorted would be broken up into smaller subarrays and each subarray would be sorted with insertion sort. Then the subarrays would be merged. This is exactly what the animation is showing.
There is no good reason to remove this animation. It just needed a more descriptive caption. It has been in this article since at least 2013. Jrheller1 ( talk) 23:49, 19 March 2019 (UTC)
The currently still visible animated image conflicts with the algorithms presented in the article. What the animation depicts is a merge sort implemented using a queue instead of a stack (recursion). A queue based implementation results in a breadth first repeated splitting of the array until the size of runs is reduced to 1 element per run. The queue approach is not normally done because the queue space complexity is O(n), and the queue approach is not mentioned anywhere in the article. A stack approach is depth first, left first: the array split in two, the left half split in two, the left quarter split in two, ..., then and only when the leftmost two runs of size 1 are produced does the merge process begin, following the stack chain up and dawn in a depth first, left first order. A simpler fix would be to show a bottom up approach. In one step, the initial array is separated into n runs of size 1 (this is really not a step, as the array is just treated as n runs of size 1 without any actual data manipulation), then typically even and odd runs are merged in breadth first order. This would only require removing the intermediate split steps shown in the animation. Rcgldr ( talk) 21:42, 21 March 2019 (UTC)
[0 1] [0 1][2 3] [0 1 2 3] [0 1 2 3][4 5] [0 1 2 3][4 5][6 7] [0 1 2 3][4 5 6 7] [0 1 2 3 4 5 6 7] [0 1 2 3 4 5 6 7][8 9] [0 1 2 3 4 5 6 7][8 9][10 11] [0 1 2 3 4 5 6 7][8 9 10 11] [0 1 2 3 4 5 6 7][8 9 10 11][12 13] [0 1 2 3 4 5 6 7][8 9 10 11][12 13][14 15] [0 1 2 3 4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
[0 1][2 3][4 5][6 7][8 9][10 11][12 13][14 15] [0 1 2 3][4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
[0 1 2 3 4 5 6 7] [0 1 2 3] [0 1] [0][1] {0 1} [2 3] [2][3] {2 3} {0 1 2 3} [4 5 6 7] [4 5] [4][5] {4 5} [6 7] [6][7] {6 7} {4 5 6 7} {0 1 2 3 4 5 6 7}
[0 1 2 3 4 5 6 7] [0][1][2][3][4][5][6][7] {0 1} {2 3} {4 5} {6 7} {0 1 2 3} {4 5 6 7} {0 1 2 3 4 5 6 7}
[0 1 2 3 4 5 6 7] [0 1 2 3] [4 5 6 7] [0 1] [2 3] [4 5] [6 7] [0] [1] [2] [3] [4] [5] [6] [7] {0 1} {2 3} {4 5} {6 7} {0 1 2 3} {4 5 6 7} {0 1 2 3 4 5 6 7}
Rcgldr is discussing the animation still visible in the article. The deleted animation is showing a tiled merge sort. See the section "Optimizing merge sort". It looks like subarrays of about size 16 are sorted with insertion sort and then the sorted subarrays are merged. Maybe the deleted animation should be moved down to this section with caption indicating that it is a tiled merge sort. Jrheller1 ( talk) 01:55, 22 March 2019 (UTC)
Consider that C, C++, C#, Java, Python, all handle array names as references, and can implement swap(A,B) which just swaps the references, so why not change the article to use swap(A,B), and put in a comment about using copy for programming languages that wouldn't support a swap. Rcgldr ( talk) 18:22, 10 June 2019 (UTC)
A
and B
are not 'references' to objects but rather names of variables. You can't just swap the meaning of the two to make them refer to opposite data. You'd have to replace pure arrays with pointers to arays and that would overwhelm the whole code with lots of unnecessary dereference operatos (prefix asterisks). As a result – IMHO – the code would be less readable, whilst readability should be one of the main aims of presenting the code in encyclopedia. Leave minor optimizations to programming handbooks. --
CiaPan (
talk)
06:10, 11 June 2019 (UTC)
A[]
to B[]
, then reverses the parameters on the recursive calls so that the direction merge changes with the level of recursion.
Rcgldr (
talk)
09:51, 15 June 2019 (UTC)A[]
and B[]
are passed as parameters to a function. In C or C++, arrays passed as parameters are treated as pointers, myfun(int A[], int B[], ...) is the same as myfun(int *A, int *B, ...). Using sizeof(A) within myfun returns the size of a pointer, not the size of the array, so for C or C++, a 3rd parameter would be needed for the number of elements. Bottom up merge sort could use a counter for the number of passes and do a copy if the number of passes are odd, or similar to the top down example, which always copies at the start, bottom up could always copy at the end.
Rcgldr (
talk)
13:40, 11 June 2019 (UTC)Er... I just had a look at this talk page and noticed the extensive discussion of multiple versions of example code, after I just rewrote it.
As the commit message says, the motivation for the rewrite was TopDownSplitMerge()
, which was:
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
// merge the resulting runs from array B[] into A[]
TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}
This expects the recursive calls to TopDownSplitMerge
to take their input from A[]
and leave their results in B[]
, so the call to TopDownMerge()
can copy them back into A[]
. This implements an in-place sort. But didn't we just say that it needs TopDownSplitMerge
to be an out-of-place sort?
Upon even more reflection, it might be that the comment is seriously misleading and the code actually works in an incredibly confusing way because A[]
and B[]
are duplicates of each other so we recurse down to the bottom and find the source data in either A
or B
depending on the number of levels of recursion and then things work on the way back up. But if I've stared at it for half an hour and still can't understand it, that's not a good pedagogical example. (And
q:Norm Schryer's wisdom applies.)
Almost as significantly, it uses a temporary buffer equal to the input size, which is a completely impractical implementation. We want to avoid confusing micro-optimizations (like special-casing small arrays), but using a temporary buffer of realistic size has a pretty fundamental effect on how the code is organized. You want to give an example whose structure is recognizably similar to a practical implementation.
The list code wasn't in such bad shape, but I didn't like how the top-down and bottom-up list code used different abstractions for the lists. Such gratuitous differences make it difficult for a reader to see the significant differences. One thing I specifically did was use the same core Merge
operations in both examples.
I spent a while thinking about it and think I came up with pretty concise and clear implementations which don't leave out anything important (fiddly corner cases like zero-sized input are handled). But given the amount of discussion which has taken place here, I probably should have proposed it here for discussion rather than just editing it into the article. Oops.
One thing I'm not happy with and still needs fixing is the function names; the array and list sort functions currently have the same names. Fortunately, that's a sufficiently minor point that it doesn't do significant harm to the article pending resolution. I'm also not happy with the obscure bit-twiddling in the lsbit()
function. I put it in its own function and commented the hell out of it, but I can't find an existing article to link to.
Another problem which needs fixing is that the tape-based merging description refers to the bottom-up example code, but the example code (both before and after my rewrite) uses a depth-first merge order. Tape merging operates breadth-first. I at least added a few words about the difference (cut short before I digressed into cache-aware multi-way merges), but the tape merging reference needs fixed. Update: I fixed this.
Anyway, sorry for dropping a bomb into the article. I'm used to editing quiet articles where the talk page is overrun with tumbleweeds and asking for comments there is a months-long process. so it's WP:BOLD or go home. I should have checked this one first. 196.247.24.22 ( talk) 00:50, 22 December 2019 (UTC)
I'm leaving a note here since obviously there's been a lot of work done but the change I'm making is rather minor. I've skimmed over the most recent discussion in particular and don't think I've missed any discussion of this but of course I could be mistaken.
In doing an implementation, I noticed an off-by-one error: in checking for size one, the difference of the indices is compared against 2. But the indices are inclusive I believe, so if we have, for instance, 0 & 1, the difference is 1 but the size is 2. I think this bug slipped in when going from a function which checked length to using array indices where it's calculated but I haven't checked the history to confirm that.
So, I'm going to change the value there to 1 from 2 as I believe that's the correct comparison (that is: if b-a < 1, then we have 1 (or fewer) elements and don't need to split/merge).
Écrivan renaissant ( talk) 06:28, 17 July 2020 (UTC)
TopDownSplitMerge
you modified explicitly says:
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
@ Écrivan renaissant: Another editor fixed that: special:diff/968920370. -- CiaPan ( talk) 20:30, 5 August 2020 (UTC)
In sub section Use with tape drives, there seems to be an incomplete reference (currently note 11):
<ref>Selection sort. Knuth's snowplow. Natural merge.</ref>
-- Mortense ( talk) 21:00, 20 November 2020 (UTC)
@ Mortense and Glrx: I've added the reference, at last: Special:Diff/1022865342. Better late than never. CiaPan ( talk) 23:30, 12 May 2021 (UTC)
For example, one of the operations of the 1937 IBM 077 punched card collator was to merge two already sorted decks of cards. It could also remove duplicates. However, I haven't been able to find out if merge sort was inspired by the merge operation of such collators. Rcgldr ( talk) 18:09, 12 May 2021 (UTC)
The analysis of the worst-case number T of comparisons of keys performed by Merge sort is incorrect.
It begins from an incorrect recurrence relation
on T. First, the said recurrence relation is different for the worst case, the average case, and the best case. Second, it is formally invalid, except for the cases when n is a power of 2 (because T requires integer arguments and n/2 is not an integer if n is odd). Third, it mishandles the basis case of n = 1. And the reference
[1] that is supposed to justify it is invalid as it does not imply it. [This sentence was added by
M A Suchenek (
talk)
20:14, 8 June 2021 (UTC).]
The correct recurrence relation the worst-case number of comparisons of keys performed by Merge sort on n distinct elements is
for and
As I mentioned before, the n-element array cannot be split on two subarrays of equal size n/2 if n is odd, simply because an array cannot have a size that is not an integer number. For instance, if n = 3 then the array is split on two subarrays of sizes and , and not on two arrays of size 1.5.
Also, the worst-case number of comparisons of keys while merging two sorted lists of the total size n is n-1 and not n. For instance, merging two 1-elemet lists (thus having a total of 2 elements) requires 1 comparison of keys and not 2 comparisons.
The comment that Knuth's analysis is incorrect because Knuth allegedly used "slightly suboptimal" version of Merge sort was left unexplained. As a result, it remains unclear what Merge sort is being analyzed in the section "Analysis". The standard version of Merge sort that satisfies the standard (given above) recurrence relation for has the exact worst-case performance (and not "slightly" better than) given by Knuth. M A Suchenek ( talk) 21:18, 1 June 2021 (UTC)
MrOllie: Your argument (above) is self-contradictory and, therefore, invalid.
First, you removed my insertion of relevant material with published proof claiming that the reference was not "reliable". Then you justified the removal with a reference to Wikipedia:Verifiability, not truth page that is in itself unreliable, unverifiable and, as a matter of fact, comprises of advises and opinions of some individuals of unknown credibility, as the following quote (with emphases added) from the top of that page Wikipedia:Verifiability, not truth clearly indicates:
You continued justifying removal of my addition by pointing to Wikipedia page WP:NOR "No original research" while the entire article that I added to has a disclaimer on the very top stating:
Thus you don't pass your own standards that you are trying to impose on me.
Then you go on claiming that the proved truthfulness of my insert doesn't matter because its published proof does not come form a "reliable" reference. This assertion of yours that the truth is secondary to credibility of the instrument of its publication is not just absurd; it goes against the mainstream methodology of modern science and - particularly - mathematics. The exact formula for the best-case performance of Merge sort has a published (in arxiv.org [2]) proof that is verifiable by anyone with sufficient college math preparation and enough IQ. Removing it was an act of suppression of objective (and verifiable) knowledge under doctrine that it comes from an unapproved by you source. Such an action falls into category of censorship.
Moreover, you apparently use double standard which material fits for inclusion in Wikipedia pages and which does not. On one hand, you removed objectively true material that I posted, despite that it has a published proof [2], but at the same time you let false information in the same section of the article (as I indicated above) to remain included despite that it has no relevant reference to any credible source that would validate it, and despite the direction on the top of the article (quoted above) that such information has to be removed. So when it comes to obviously false statements in the article, like a claim (with a mostly irrelevant reference) that the recurrence relation for Merge sort is:
or the comment (with an irrelevant reference) that Knuth's analysis is incorrect because Knuth allegedly used "slightly suboptimal" version of Merge sort (which statement contradicts the standard definition of Merge sort that is characterized by the recurrence relation (see [3])
and
you are oblivious to the fact that they are not only lacking references but are false, yet you give yourself an mandate to remove my contribution because the reference with verifiable proof that I provided [2] does not meet your absurd standard of source credibility.
Once again, you don't obey the very standards that you expect others to follow. I wonder where does your "authority" to impose those standards on others while exempting yourself from them come from?
Your comment about my "conflict of interest" is not just an unproven allegation, but it is utterly absurd. (I suppose you do not understand what is the legal meaning of the term "conflict of interest".) Your misguided comment implies that I am somehow not allowed (by what authority?) to refer to proofs that I have constructed and published [2]. Based on clearly double standard that you exhibited in this discussion and your obvious bias that favors false statements of your liking over provably true statements that you reject, I suppose that your accusing me of "conflict of interest" is psychological projection.
Your comment about anyone being able to publish anything on arxiv.com is false, as it is irrelevant. Because a proof is a proof no matter how it was published, as long as it was published in a way that allows unrestricted and stable public access to it.
Due to your misguided actions, the article Merge sort, section Analysis, is of substandard quality.
M A Suchenek ( talk) 20:14, 8 June 2021 (UTC)
There is nothing there that would suggest that referring to one's own published proofs of mathematical facts qualifies as "conflict of interest". Got it?– you are wrong (and rude, too.) Citing yourself not always qualifies as COI, but it well may be considered as such, and the policy says it explicitly. Please see WP:SELFCITE. It may also qualify as self-promotion, which is one of things Wikipedia is not.
For the record, here is the body of my insert that was deleted:
The recurrence relation on the best-case number of comparisons of keys performed by Merge sort on n distinct elements is given by:
and
To understand it, it suffices to note that in the best case, each element of the shorter of the two merged lists must be compared to an element of the other list.
Solving the above recurrence relation turns out quite tricky, and is more involved than solving the recurrence relation for the worst-case. It has been done, for instance, in [2]:
where is a continuous real function that oscillates like a zigzag between 0 and and is given by:
In particular, for relatively small n, is substantially larger than (or, in other words, is substantially larger than half of ), as the following inequality derived for any n in [2] shows:
As n, and , converge to ∞, the ratio of above difference to converges to zero, that is, for large n, is roughly equal to, although larger than, half of
References
I just randomly stumbled upon the OR tag. I have to agree with MrOllie. You can't use your own unpublished research as a citation here. I'd cite the relevant wiki policy, but MrOllie did this already. Stix1776 ( talk) 10:59, 23 June 2022 (UTC)
I am new to C++ and Wikipedia editing, (have been loosing sleep trying to find these bugs) so do not have the confidence to make this edit:- I think there is an error in the TopDownMerge, the first if statement I think should not read
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
but
if (i <= iMiddle && (j > iEnd || A[i] <= A[j])) {
Reasoning:- If the array has 2 elements i(0) will be equal to iMiddle(0) and j(1) will be equal to iEnd(1). On the first pass the first statement will now be true, the second will be false. The size of each element now determines which is copied into the other array first.
Rthepb ( talk) 14:42, 25 November 2021 (UTC)
Is this section needed or should the section note that most implementations of merge sort already incorporate a similar concept. The top down merge sort example (for arrays) avoids copy back by changing the direction of merge for each level of recursion (it does do an initial copy, but mutually recursive functions can be used to avoid the initial copy). The bottom up merge sort example mentions this in a comment that swapping pointers would avoid the shown copy back loop. The first two passes of a bottom up merge sort are the equivalent of a ping pong merge sort. Alternating direction of merge operations for merge sort dates back to the early 1960's (or earlier) for tape sorts using merge sort or polyphase merge sort. Rcgldr ( talk) 18:34, 10 January 2023 (UTC)
Worst case of time complexity for this algorithm is n*lg(n) according to Introduction to Algorithms. Not n*log(n) as noted in Analysis section. -- Siavoshkc ( talk) 17:22, 24 September 2023 (UTC)
Instead of scanning of lists to split them in half, a list size integer value is divided by 2 for each level of recursion, until a base case where size == 1, where a pointer | iterator to the next node is returned. The recursive merge sort updates (pass by reference) a pointer | iterator to the beginning node and returns a pointer | iterator to the ending node of a sorted list. Visual Studio 2022 switched to this method for std::list::sort. The following is a C++ example using iterators. Iterator names: li = left run iterator, ri = right run iterator = end left run iterator, ei = end right run iterator. Merge will splice (move and insert) sub-lists (multiple nodes) from right run, to left run for right run values < current left run value, else it just advances left run iterator. Splice requires a doubly linked list.
template <typename T> typename std::list<T>::iterator Merge(std::list<T> &ll, typename std::list<T>::iterator li, typename std::list<T>::iterator ri, typename std::list<T>::iterator ei) { std::list<T>::iterator si; std::list<T>::iterator ni; ni = (*ri < *li) ? ri : li; while(1){ if(*ri < *li){ for(si = std::next(ri); si != ei && *si < *li; si++); ll.splice(li, ll, ri, si); ri = si; if(ri == ei) return ni; } else { if(++li == ri) return ni; } } } template <typename T> typename std::list<T>::iterator SortListR(std::list<T> &ll, typename std::list<T>::iterator &li, size_t size) { if (size == 1) return std::next(li); std::list<T>::iterator ri; std::list<T>::iterator ei; ri = SortListR(ll, li, size-size/2); ei = SortListR(ll, ri, size/2); li = Merge(ll, li, ri, ei); return ei; } template <typename T> void SortList(std::list<T> &ll) { if (ll.size() < 2) // return if nothing to do return; SortListR(ll, ll.begin(), ll.size()); }
This is the
talk page for discussing improvements to the
Merge sort article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1 |
Daily pageviews of this article
A graph should have been displayed here but
graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at
pageviews.wmcloud.org |
This
level-5 vital article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
The article mentions a running time of for in-place merge sort, which is wrong. It should be . — Preceding unsigned comment added by Dhruvbird ( talk • contribs) 04:40, 16 March 2015 (UTC)
Two sorted arrays can be merged in place in O(n) time, using O(1) space (temporary variable to swap two elements). To implement mergesort, this merge needs to be repeated log(n) times. You can easily implement mergesort bottom-up stably and in-place. Start with n=1, and merge the slices from i*n to i*(n+1) for i=0 until you exhaust the array. For n=1 this sorts pairs of elements. Then multiply n by 2 and restart until n >= size of the array. — Preceding unsigned comment added by 87.198.115.102 ( talk) 07:53, 26 June 2013 (UTC)
I would second the first posters observation. Its nothing more than an afternoon's coding to get the solution. Think about how it works for a linked list and I you'll get inference for static data, just as the first poster observed. Merge sorts are not in a category of algorithms considered hard to implement, even when they are hybrid. — Preceding unsigned comment added by 80.254.148.163 ( talk) 17:44, 13 June 2014 (UTC)
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
This is Theta(n^2) with Theta(n) merges and Theta(n) complexity in reinsert. 188.120.84.157 ( talk) 04:42, 26 April 2014 (UTC)
It is claimed that the algorithm was invented by von Neumann in 1945. However the reference is to the Knuth book from 1998 (not the first edition, by the way!!!). The reference to an original work performed by von Neumann and published in 1945 is necessary. If the algorithm presented is described only in the Knuth book from 1998, it's from 1998, not from 1945! Riemann'sZeta ( talk) 20:11, 12 April 2011 (UTC)
As an algorithm that can be done recursively and non-recusively, it seems to me that added an example of a non-recursive merge sort algorithm might make this article more complete. I myself am not particularly apt at writing clear and understandable pseudocode, but I feel an example hear would be a good idea. OceanicMeerkat ( talk) 05:52, 27 January 2014 (UTC)
Just try to write that for the real computer. One of the obvious errors is that it splits [0, mid], [mid + 1, high] but then merges [0, mid - 1], [mid, high] — Preceding unsigned comment added by 86.57.194.198 ( talk) 06:28, 18 March 2014 (UTC)
Conceptually if you divide anything into two halves around a (truncated integer) midpoint then the first half will be "begin" to "midpoint", the second half will be "midpoint + 1" to "end". For example, begin = 0, end = 1, midpoint is 0, "left half" is 0, "right half" is 1. With the current code "left half" would be 0, "right half" would be 0 and 1, i.e. the entire list.
In Cracking the Coding Interview, p.118, which uses very similar code to the WP example, the first half is "begin to midpoint", the second half is "midpoint + 1 to end", as I would expect.
I changed right half to midpoint + 1, but my change was reverted by
User:Glrx with the comment "inclusive/exclusive indices". Later in the WP code there is a comment: "https:// left half is A[iBegin :iMiddle-1] // right half is A[iMiddle:iEnd-1 ]." But I don't think that works with truncated integers; in my example of a two element list, left half would be from 0 to -1, i.e. you've walked off the array. It would work with integers which round up, but that's not the case with C style languages, which appears to be the style the code is written in.
Also, even if we were rounding up, the comment implies that the midpoint is only in the right half, whereas with the code as written, it's actually in both halves. Can anyone enlighten me what's going on here? --
Merlinme (
talk)
20:32, 8 December 2014 (UTC)
This is a new article section. It's the primary method used to sort linked lists so it should be included in the article. Implementations of C++ STL (standard template library) function std::list::sort()use this algorithm. Rcgldr ( talk) 00:37, 23 November 2015 (UTC)
Anyone else think the animation example has extraneous comparisons once one of the sides (the left side in all cases) runs out of cells? I thought the point of the whole algorithm is to take advantage of the fact that the partitions being merged are sorted. — Preceding unsigned comment added by 88.192.22.239 ( talk) 14:56, 14 April 2016 (UTC)
Also - the animation appears to be wrong. It does not follow the Top-Down example code because it keeps going back to other, parallel arrays and working on them INSTEAD OF fully sorting the left subarray AND ONLY THEN going back and sorting the right subarray. — Preceding unsigned comment added by 73.157.112.58 ( talk) 02:14, 18 December 2021 (UTC)
The article is completely obscure to those of us who can't read computer code. You break down the list into sub-lists, then you merge them - but how does that work? How do you merge two sorted lists into one? The article just assumes that's easy, as far as the text is concerned. The diagram also shows lists simply being merged and emerging as sorted, without explanation of the merge process. Cyclopaedic ( talk) 09:07, 2 August 2016 (UTC)
I've reverted the midpoint formula back to the clearer (a+b)/2
. The a+(b-a)/2
form is not obvious to most people.
WP should be describing algorithms. In a pseuodcode implementation, the widths of the numbers are not specified because the operations are abstract. The calculations are presumed to not overflow.
Also, the URL https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html is a blog. It is not a reliable source.
At Binary search algorithm#Implementation issues, a big point is made of the Java library bug, but that claim is disingenuous. There's a reason the bug was not discovered for years: it would only occur if somebody did something impractical. It would only be serious issue when one uses 32-bit indices in a 64-bit address space. But indices in 64-bit address spaces should be 64-bit numbers. In a 64-address space, I might want to make an array of more than 232 records; I should be able to use binary search on that array. If the system is only allowing 32-bit indices, then I have bigger problems.
Now the meat.
The numbers used in the algorithm are indices rather than byte pointers. In rational cases, the size of a record will be at least 4 bytes. So in the 32-bit address space case, the record indices will be 30-bit numbers. Overflow will not be an issue. Same for the 64-bit address space.
The Java bug manufactured an irrational case: it made an array of 1.1 billion single bytes and tried to search that array; the numbers overflowed and generated an array-out-of-bounds reference. Think about that array of bytes for a minute. A binary search of an array with 1.1 billion items that can only have 256 distinct items?
WP should not be emphasizing such didactic corner cases. Glrx ( talk) 20:02, 10 October 2017 (UTC)
This section includes the statements: "... producing an in-place merge algorithm that can be combined with a standard (top-down or bottom-up) merge sort ... " "the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage", but logarithmic stack space is only used by top down merge sort, not by bottom up merge sort. Rcgldr ( talk) 16:43, 9 December 2017 (UTC)
Hoping I'm not missing something here, but after going through it many times I think there's something missing in the Top-Down example as of the May 24 2018 edit.
If you do the sort with an array of size 16, then the resulting sorted array ends up in the original array (the one that was "A" in TopDownMergeSort at the top).
...but if you do the sort with an array of size 8, then the resulting sorted array ends up in the work array (the one thas was "B" in TopDownMergeSort at the top).
There is no piece at the end that figures out if the result lies on the wrong array, and copies it over if that's the case.
Jlkeegan ( talk) 03:57, 15 June 2018 (UTC)
A
and B
swap on each level of recursion, as TopDownSplitMerge(B[], iBegin, iEnd, A[])
invokes itself with TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
A
means a source array for split and a destination array for merge at the current level of recursion which can be either the same as the destination array of the whole processing or the working (temporary) copy of source data made at the beginning. And similary (but opposite) for B
, which is a temporary source array for merging at the current level of recursion. Whether it is this or that way depends on whether it is even or odd level of recursion. --
CiaPan (
talk)
08:51, 15 June 2018 (UTC)TopDownSplitMerge
passes its A[]
argument as the last parameter to TopDownMerge
. As a result, the very last merge puts the merged data to the original destination array. Which is correct. It doesn't matter how long the array is – whether it contains two, three, eight, sixteen or a million items – and how many levels of recursion are involved, the final merge always puts data into the correct array. --
CiaPan (
talk)
10:43, 18 June 2018 (UTC)@ CiaPan: Copied from my talk page:
Hi, you have removed File:Merge sort animation2.gif here: Special:Diff/887750333.
Why do you think it's not a mergesort depiction? --CiaPan (talk) 3:10 am, Today (UTC−4)
(I removed it in one other place; not sure why I didn't give as detailed an explanation here). My issue is that it doesn't show the actual merging of sublists, which instead appears to happen instantaneously. In contrast, the animation in the infobox does show the merging. – Deacon Vorbis ( carbon • videos) 12:22, 15 March 2019 (UTC)
The deleted animation is showing the merge sort of an array of random integers. The caption before I changed it didn't indicate at all what was being sorted. The deleted animation is actually more realistic than the other one in this article. In an actual merge sort, the array to be sorted would be broken up into smaller subarrays and each subarray would be sorted with insertion sort. Then the subarrays would be merged. This is exactly what the animation is showing.
There is no good reason to remove this animation. It just needed a more descriptive caption. It has been in this article since at least 2013. Jrheller1 ( talk) 23:49, 19 March 2019 (UTC)
The currently still visible animated image conflicts with the algorithms presented in the article. What the animation depicts is a merge sort implemented using a queue instead of a stack (recursion). A queue based implementation results in a breadth first repeated splitting of the array until the size of runs is reduced to 1 element per run. The queue approach is not normally done because the queue space complexity is O(n), and the queue approach is not mentioned anywhere in the article. A stack approach is depth first, left first: the array split in two, the left half split in two, the left quarter split in two, ..., then and only when the leftmost two runs of size 1 are produced does the merge process begin, following the stack chain up and dawn in a depth first, left first order. A simpler fix would be to show a bottom up approach. In one step, the initial array is separated into n runs of size 1 (this is really not a step, as the array is just treated as n runs of size 1 without any actual data manipulation), then typically even and odd runs are merged in breadth first order. This would only require removing the intermediate split steps shown in the animation. Rcgldr ( talk) 21:42, 21 March 2019 (UTC)
[0 1] [0 1][2 3] [0 1 2 3] [0 1 2 3][4 5] [0 1 2 3][4 5][6 7] [0 1 2 3][4 5 6 7] [0 1 2 3 4 5 6 7] [0 1 2 3 4 5 6 7][8 9] [0 1 2 3 4 5 6 7][8 9][10 11] [0 1 2 3 4 5 6 7][8 9 10 11] [0 1 2 3 4 5 6 7][8 9 10 11][12 13] [0 1 2 3 4 5 6 7][8 9 10 11][12 13][14 15] [0 1 2 3 4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
[0 1][2 3][4 5][6 7][8 9][10 11][12 13][14 15] [0 1 2 3][4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
[0 1 2 3 4 5 6 7] [0 1 2 3] [0 1] [0][1] {0 1} [2 3] [2][3] {2 3} {0 1 2 3} [4 5 6 7] [4 5] [4][5] {4 5} [6 7] [6][7] {6 7} {4 5 6 7} {0 1 2 3 4 5 6 7}
[0 1 2 3 4 5 6 7] [0][1][2][3][4][5][6][7] {0 1} {2 3} {4 5} {6 7} {0 1 2 3} {4 5 6 7} {0 1 2 3 4 5 6 7}
[0 1 2 3 4 5 6 7] [0 1 2 3] [4 5 6 7] [0 1] [2 3] [4 5] [6 7] [0] [1] [2] [3] [4] [5] [6] [7] {0 1} {2 3} {4 5} {6 7} {0 1 2 3} {4 5 6 7} {0 1 2 3 4 5 6 7}
Rcgldr is discussing the animation still visible in the article. The deleted animation is showing a tiled merge sort. See the section "Optimizing merge sort". It looks like subarrays of about size 16 are sorted with insertion sort and then the sorted subarrays are merged. Maybe the deleted animation should be moved down to this section with caption indicating that it is a tiled merge sort. Jrheller1 ( talk) 01:55, 22 March 2019 (UTC)
Consider that C, C++, C#, Java, Python, all handle array names as references, and can implement swap(A,B) which just swaps the references, so why not change the article to use swap(A,B), and put in a comment about using copy for programming languages that wouldn't support a swap. Rcgldr ( talk) 18:22, 10 June 2019 (UTC)
A
and B
are not 'references' to objects but rather names of variables. You can't just swap the meaning of the two to make them refer to opposite data. You'd have to replace pure arrays with pointers to arays and that would overwhelm the whole code with lots of unnecessary dereference operatos (prefix asterisks). As a result – IMHO – the code would be less readable, whilst readability should be one of the main aims of presenting the code in encyclopedia. Leave minor optimizations to programming handbooks. --
CiaPan (
talk)
06:10, 11 June 2019 (UTC)
A[]
to B[]
, then reverses the parameters on the recursive calls so that the direction merge changes with the level of recursion.
Rcgldr (
talk)
09:51, 15 June 2019 (UTC)A[]
and B[]
are passed as parameters to a function. In C or C++, arrays passed as parameters are treated as pointers, myfun(int A[], int B[], ...) is the same as myfun(int *A, int *B, ...). Using sizeof(A) within myfun returns the size of a pointer, not the size of the array, so for C or C++, a 3rd parameter would be needed for the number of elements. Bottom up merge sort could use a counter for the number of passes and do a copy if the number of passes are odd, or similar to the top down example, which always copies at the start, bottom up could always copy at the end.
Rcgldr (
talk)
13:40, 11 June 2019 (UTC)Er... I just had a look at this talk page and noticed the extensive discussion of multiple versions of example code, after I just rewrote it.
As the commit message says, the motivation for the rewrite was TopDownSplitMerge()
, which was:
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
// merge the resulting runs from array B[] into A[]
TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}
This expects the recursive calls to TopDownSplitMerge
to take their input from A[]
and leave their results in B[]
, so the call to TopDownMerge()
can copy them back into A[]
. This implements an in-place sort. But didn't we just say that it needs TopDownSplitMerge
to be an out-of-place sort?
Upon even more reflection, it might be that the comment is seriously misleading and the code actually works in an incredibly confusing way because A[]
and B[]
are duplicates of each other so we recurse down to the bottom and find the source data in either A
or B
depending on the number of levels of recursion and then things work on the way back up. But if I've stared at it for half an hour and still can't understand it, that's not a good pedagogical example. (And
q:Norm Schryer's wisdom applies.)
Almost as significantly, it uses a temporary buffer equal to the input size, which is a completely impractical implementation. We want to avoid confusing micro-optimizations (like special-casing small arrays), but using a temporary buffer of realistic size has a pretty fundamental effect on how the code is organized. You want to give an example whose structure is recognizably similar to a practical implementation.
The list code wasn't in such bad shape, but I didn't like how the top-down and bottom-up list code used different abstractions for the lists. Such gratuitous differences make it difficult for a reader to see the significant differences. One thing I specifically did was use the same core Merge
operations in both examples.
I spent a while thinking about it and think I came up with pretty concise and clear implementations which don't leave out anything important (fiddly corner cases like zero-sized input are handled). But given the amount of discussion which has taken place here, I probably should have proposed it here for discussion rather than just editing it into the article. Oops.
One thing I'm not happy with and still needs fixing is the function names; the array and list sort functions currently have the same names. Fortunately, that's a sufficiently minor point that it doesn't do significant harm to the article pending resolution. I'm also not happy with the obscure bit-twiddling in the lsbit()
function. I put it in its own function and commented the hell out of it, but I can't find an existing article to link to.
Another problem which needs fixing is that the tape-based merging description refers to the bottom-up example code, but the example code (both before and after my rewrite) uses a depth-first merge order. Tape merging operates breadth-first. I at least added a few words about the difference (cut short before I digressed into cache-aware multi-way merges), but the tape merging reference needs fixed. Update: I fixed this.
Anyway, sorry for dropping a bomb into the article. I'm used to editing quiet articles where the talk page is overrun with tumbleweeds and asking for comments there is a months-long process. so it's WP:BOLD or go home. I should have checked this one first. 196.247.24.22 ( talk) 00:50, 22 December 2019 (UTC)
I'm leaving a note here since obviously there's been a lot of work done but the change I'm making is rather minor. I've skimmed over the most recent discussion in particular and don't think I've missed any discussion of this but of course I could be mistaken.
In doing an implementation, I noticed an off-by-one error: in checking for size one, the difference of the indices is compared against 2. But the indices are inclusive I believe, so if we have, for instance, 0 & 1, the difference is 1 but the size is 2. I think this bug slipped in when going from a function which checked length to using array indices where it's calculated but I haven't checked the history to confirm that.
So, I'm going to change the value there to 1 from 2 as I believe that's the correct comparison (that is: if b-a < 1, then we have 1 (or fewer) elements and don't need to split/merge).
Écrivan renaissant ( talk) 06:28, 17 July 2020 (UTC)
TopDownSplitMerge
you modified explicitly says:
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
@ Écrivan renaissant: Another editor fixed that: special:diff/968920370. -- CiaPan ( talk) 20:30, 5 August 2020 (UTC)
In sub section Use with tape drives, there seems to be an incomplete reference (currently note 11):
<ref>Selection sort. Knuth's snowplow. Natural merge.</ref>
-- Mortense ( talk) 21:00, 20 November 2020 (UTC)
@ Mortense and Glrx: I've added the reference, at last: Special:Diff/1022865342. Better late than never. CiaPan ( talk) 23:30, 12 May 2021 (UTC)
For example, one of the operations of the 1937 IBM 077 punched card collator was to merge two already sorted decks of cards. It could also remove duplicates. However, I haven't been able to find out if merge sort was inspired by the merge operation of such collators. Rcgldr ( talk) 18:09, 12 May 2021 (UTC)
The analysis of the worst-case number T of comparisons of keys performed by Merge sort is incorrect.
It begins from an incorrect recurrence relation
on T. First, the said recurrence relation is different for the worst case, the average case, and the best case. Second, it is formally invalid, except for the cases when n is a power of 2 (because T requires integer arguments and n/2 is not an integer if n is odd). Third, it mishandles the basis case of n = 1. And the reference
[1] that is supposed to justify it is invalid as it does not imply it. [This sentence was added by
M A Suchenek (
talk)
20:14, 8 June 2021 (UTC).]
The correct recurrence relation the worst-case number of comparisons of keys performed by Merge sort on n distinct elements is
for and
As I mentioned before, the n-element array cannot be split on two subarrays of equal size n/2 if n is odd, simply because an array cannot have a size that is not an integer number. For instance, if n = 3 then the array is split on two subarrays of sizes and , and not on two arrays of size 1.5.
Also, the worst-case number of comparisons of keys while merging two sorted lists of the total size n is n-1 and not n. For instance, merging two 1-elemet lists (thus having a total of 2 elements) requires 1 comparison of keys and not 2 comparisons.
The comment that Knuth's analysis is incorrect because Knuth allegedly used "slightly suboptimal" version of Merge sort was left unexplained. As a result, it remains unclear what Merge sort is being analyzed in the section "Analysis". The standard version of Merge sort that satisfies the standard (given above) recurrence relation for has the exact worst-case performance (and not "slightly" better than) given by Knuth. M A Suchenek ( talk) 21:18, 1 June 2021 (UTC)
MrOllie: Your argument (above) is self-contradictory and, therefore, invalid.
First, you removed my insertion of relevant material with published proof claiming that the reference was not "reliable". Then you justified the removal with a reference to Wikipedia:Verifiability, not truth page that is in itself unreliable, unverifiable and, as a matter of fact, comprises of advises and opinions of some individuals of unknown credibility, as the following quote (with emphases added) from the top of that page Wikipedia:Verifiability, not truth clearly indicates:
You continued justifying removal of my addition by pointing to Wikipedia page WP:NOR "No original research" while the entire article that I added to has a disclaimer on the very top stating:
Thus you don't pass your own standards that you are trying to impose on me.
Then you go on claiming that the proved truthfulness of my insert doesn't matter because its published proof does not come form a "reliable" reference. This assertion of yours that the truth is secondary to credibility of the instrument of its publication is not just absurd; it goes against the mainstream methodology of modern science and - particularly - mathematics. The exact formula for the best-case performance of Merge sort has a published (in arxiv.org [2]) proof that is verifiable by anyone with sufficient college math preparation and enough IQ. Removing it was an act of suppression of objective (and verifiable) knowledge under doctrine that it comes from an unapproved by you source. Such an action falls into category of censorship.
Moreover, you apparently use double standard which material fits for inclusion in Wikipedia pages and which does not. On one hand, you removed objectively true material that I posted, despite that it has a published proof [2], but at the same time you let false information in the same section of the article (as I indicated above) to remain included despite that it has no relevant reference to any credible source that would validate it, and despite the direction on the top of the article (quoted above) that such information has to be removed. So when it comes to obviously false statements in the article, like a claim (with a mostly irrelevant reference) that the recurrence relation for Merge sort is:
or the comment (with an irrelevant reference) that Knuth's analysis is incorrect because Knuth allegedly used "slightly suboptimal" version of Merge sort (which statement contradicts the standard definition of Merge sort that is characterized by the recurrence relation (see [3])
and
you are oblivious to the fact that they are not only lacking references but are false, yet you give yourself an mandate to remove my contribution because the reference with verifiable proof that I provided [2] does not meet your absurd standard of source credibility.
Once again, you don't obey the very standards that you expect others to follow. I wonder where does your "authority" to impose those standards on others while exempting yourself from them come from?
Your comment about my "conflict of interest" is not just an unproven allegation, but it is utterly absurd. (I suppose you do not understand what is the legal meaning of the term "conflict of interest".) Your misguided comment implies that I am somehow not allowed (by what authority?) to refer to proofs that I have constructed and published [2]. Based on clearly double standard that you exhibited in this discussion and your obvious bias that favors false statements of your liking over provably true statements that you reject, I suppose that your accusing me of "conflict of interest" is psychological projection.
Your comment about anyone being able to publish anything on arxiv.com is false, as it is irrelevant. Because a proof is a proof no matter how it was published, as long as it was published in a way that allows unrestricted and stable public access to it.
Due to your misguided actions, the article Merge sort, section Analysis, is of substandard quality.
M A Suchenek ( talk) 20:14, 8 June 2021 (UTC)
There is nothing there that would suggest that referring to one's own published proofs of mathematical facts qualifies as "conflict of interest". Got it?– you are wrong (and rude, too.) Citing yourself not always qualifies as COI, but it well may be considered as such, and the policy says it explicitly. Please see WP:SELFCITE. It may also qualify as self-promotion, which is one of things Wikipedia is not.
For the record, here is the body of my insert that was deleted:
The recurrence relation on the best-case number of comparisons of keys performed by Merge sort on n distinct elements is given by:
and
To understand it, it suffices to note that in the best case, each element of the shorter of the two merged lists must be compared to an element of the other list.
Solving the above recurrence relation turns out quite tricky, and is more involved than solving the recurrence relation for the worst-case. It has been done, for instance, in [2]:
where is a continuous real function that oscillates like a zigzag between 0 and and is given by:
In particular, for relatively small n, is substantially larger than (or, in other words, is substantially larger than half of ), as the following inequality derived for any n in [2] shows:
As n, and , converge to ∞, the ratio of above difference to converges to zero, that is, for large n, is roughly equal to, although larger than, half of
References
I just randomly stumbled upon the OR tag. I have to agree with MrOllie. You can't use your own unpublished research as a citation here. I'd cite the relevant wiki policy, but MrOllie did this already. Stix1776 ( talk) 10:59, 23 June 2022 (UTC)
I am new to C++ and Wikipedia editing, (have been loosing sleep trying to find these bugs) so do not have the confidence to make this edit:- I think there is an error in the TopDownMerge, the first if statement I think should not read
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
but
if (i <= iMiddle && (j > iEnd || A[i] <= A[j])) {
Reasoning:- If the array has 2 elements i(0) will be equal to iMiddle(0) and j(1) will be equal to iEnd(1). On the first pass the first statement will now be true, the second will be false. The size of each element now determines which is copied into the other array first.
Rthepb ( talk) 14:42, 25 November 2021 (UTC)
Is this section needed or should the section note that most implementations of merge sort already incorporate a similar concept. The top down merge sort example (for arrays) avoids copy back by changing the direction of merge for each level of recursion (it does do an initial copy, but mutually recursive functions can be used to avoid the initial copy). The bottom up merge sort example mentions this in a comment that swapping pointers would avoid the shown copy back loop. The first two passes of a bottom up merge sort are the equivalent of a ping pong merge sort. Alternating direction of merge operations for merge sort dates back to the early 1960's (or earlier) for tape sorts using merge sort or polyphase merge sort. Rcgldr ( talk) 18:34, 10 January 2023 (UTC)
Worst case of time complexity for this algorithm is n*lg(n) according to Introduction to Algorithms. Not n*log(n) as noted in Analysis section. -- Siavoshkc ( talk) 17:22, 24 September 2023 (UTC)
Instead of scanning of lists to split them in half, a list size integer value is divided by 2 for each level of recursion, until a base case where size == 1, where a pointer | iterator to the next node is returned. The recursive merge sort updates (pass by reference) a pointer | iterator to the beginning node and returns a pointer | iterator to the ending node of a sorted list. Visual Studio 2022 switched to this method for std::list::sort. The following is a C++ example using iterators. Iterator names: li = left run iterator, ri = right run iterator = end left run iterator, ei = end right run iterator. Merge will splice (move and insert) sub-lists (multiple nodes) from right run, to left run for right run values < current left run value, else it just advances left run iterator. Splice requires a doubly linked list.
template <typename T> typename std::list<T>::iterator Merge(std::list<T> &ll, typename std::list<T>::iterator li, typename std::list<T>::iterator ri, typename std::list<T>::iterator ei) { std::list<T>::iterator si; std::list<T>::iterator ni; ni = (*ri < *li) ? ri : li; while(1){ if(*ri < *li){ for(si = std::next(ri); si != ei && *si < *li; si++); ll.splice(li, ll, ri, si); ri = si; if(ri == ei) return ni; } else { if(++li == ri) return ni; } } } template <typename T> typename std::list<T>::iterator SortListR(std::list<T> &ll, typename std::list<T>::iterator &li, size_t size) { if (size == 1) return std::next(li); std::list<T>::iterator ri; std::list<T>::iterator ei; ri = SortListR(ll, li, size-size/2); ei = SortListR(ll, ri, size/2); li = Merge(ll, li, ri, ei); return ei; } template <typename T> void SortList(std::list<T> &ll) { if (ll.size() < 2) // return if nothing to do return; SortListR(ll, ll.begin(), ll.size()); }