Talk:Merge sort/Archive 1
 | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 |
Standardization
Shouldn't this article be more structurally similar to the Insertion Sort article? --Guugolpl0x (talk) 04:00, 6 September 2010 (UTC)
Defect in Merge Pseudocode
The merge function pseudocode appears to be incorrect. If left is [2, 16] and right is [-18, 1], the result will be [-18, 1, 2]; it should be [-18, 1, 2, 16]. This could be fixed by appending the contents of left or right with a loop rather than incorrectly assuming that only one item will remain. Titaniumdecoy (talk) 00:54, 24 March 2010 (UTC)
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)
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!!!
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)
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)
References
- ^ Introduction to Algorithms, Cormen Leiserson and Rivest, McGraw Hill, 1990, p.153
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)
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)
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.
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)
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)
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);
}
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);
if(x[mid-1] <= x[mid])return; /* no need to merge */
/* 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;
}
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)
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)
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.
- The example algorithm does this, but recursively calls itself to split up a list and recurively split up sub-lists into two parts until a sublists consists of only 1 object, before any actual merging takes place. I'm not sure why it's better to push all those sub-list pointers or indexes (depending on how lists are split up) on the stack along with recursion overhead rather than just split up the list into single objects and iterate. Rcgldr (talk) 04:17, 9 January 2012 (UTC)
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).
Jeffareid 07:10, 18 September 2007 (UTC)
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)
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)
This is a python example (for readability) of in-place, stable merge sort:
def merge_sort(list, compare_function):
count = len(list)
i = 2
while i < count*2:
for join in xrange(0, count, i):
actual_size = count - join
if actual_size > i:
actual_size = i
left = join
middle = join + i/2
while left < middle and middle < (join+actual_size):
if compare_function(list[left], list[middle]) > 0:
temp = list.pop(middle)
list.insert(left, temp)
middle += 1
left += 1
i *= 2
return list
C code equivalent is this:
void merge_sort(void *array, int count, int size, int cf(void *a, void *b))
{
int i, join, actualsize;
int left, middle;
char *a = (char *)array;
char tmp_item[size];
for (i = 2; i < count*2; i *= 2)
{
for (join = 0; join < count; join += i)
{
actualsize = count - join;
if (actualsize > i)
actualsize = i;
left = join;
middle = join + i/2;
while (left < middle && middle < join+actualsize) {
if (cf(&a[left * size], &a[middle * size]) > 0) {
memcpy(tmp_item, &a[middle * size], size);
memmove(&a[(left+1) * size], &a[left * size], size*(middle-left));
memcpy(&a[left * size], tmp_item, size);
middle++;
}
left++;
}
}
}
}
4.224.252.139 (talk) 16:03, 20 December 2008 (UTC)
The memmove is called for moving size*(middle-left) bytes, which is not O(1). Therefore, the C code above is not O(n·log(n)). --Como (talk) 11:28, 15 March 2009 (UTC)
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)
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)
- Done. You are right. I see the code in the article has already been fixed as you suggested. Thanks. --68.0.124.33 (talk) 18:58, 24 September 2008 (UTC)
Random dots?
The caption for the animation states that it is sorting "random dots," but this is clearly not the case once the sorting is done (i.e., each row and column has exactly one dot in it. I think this should be a little clearer. Does anyone have an idea for better language than "Random dots"? Asmeurer (talk ♬ contribs) 23:20, 14 October 2008 (UTC)
- Well, the thing being sorted is actually a random permutation. Though "random permutation of dots" has an awkward ring to it. siℓℓy rabbit (talk) 06:35, 15 October 2008 (UTC)
What about "a random spread of dots" or something to that effect. Asmeurer (talk ♬ contribs) 18:01, 18 October 2008 (UTC)
Principle in layman's terms
The principle of mergesort is this:
- "Oh gee, sorting is a piece of cake when you have two sorted array becuase all you have to do is to merge them together!"
- "Pity they gave me this big array to sort; hmm, how can I get 2 sorted arrays from that?"
- "Ah, I've got a splendid idea! I'll just cut the big array in the middle and give the two halves away to be sorted; when they're sorted, then I merge them , and I'm done"
- "Hmm, who can I ask to sort the halves?"
- "Wait, I can sort, can't I? So I'm just going to give each half to myself!"
The last idea is the only thing that's slightly non-intuitive, because it seems as if the mergesort ought to continue giving itself stuff to sort; but since some arrays are too easy to require work (those with 0 or 1 elements), mergesort know how to do them and not pass them on.
In short, the mergesort actually either
- a) sorts the array because it is no work at all or
- b) splits the vector/array in two halves and tells itself to sort them, and then calls merge to merge the sorted halves.
--84.128.219.191 (talk) 18:07, 27 November 2008 (UTC)
Code block templates
Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:37, 7 December 2008 (UTC)
Infobox: Big-O vs. Theta
The standard implementation is , but the natural variant is only , since it takes just when the data are already sorted. The infobox should say , or add a note clarifying this point. --Como (talk) 11:54, 15 March 2009 (UTC)
Tape-sort pseudocode confusion
The merge() function in the tapesort pseudocode seems to have several inconsistencies, including references to tape[previous], current_left_record, current_right_record (as opposed to left[current], right[current]), as well as no "read next record..." in the two if-conditioned appends at the end of the routine. —Preceding unsigned comment added by 63.239.69.1 (talk) 19:42, 9 April 2009 (UTC)
Worst case complexity O(n) ?
In a short description of merge sort "Worst case space complexity" is O(n). Is this information correct? —Preceding unsigned comment added by Orfest (talk • contribs) 12:25, 25 April 2009 (UTC)
- It is absolutely correct —Preceding unsigned comment added by 80.167.145.223 (talk) 18:20, 2 February 2010 (UTC)
- Don't be confused, this is the space complexity - the auxiliary memory required in addition to the list - not the worst-case time complexity, which is what's usually implied the unqualified "worst-case complexity". Dcoetzee 03:32, 3 February 2010 (UTC)
Analysis
The article states that the complexity is O(n * log (n)) comparisons. Is this also the number of I/O requests it has to do? Since I/O takes longer than a comparison, this would be the resource I would be most interested in. 206.53.196.109 (talk) 20:56, 22 October 2009 (UTC)
- In the case of a hard drive, multiple records can be read with a single I/O, and a proper bottom up merge sort will take advantage of this. The number of I/O's per merge pass will be 2 x (number of records to be sorted) / (number of records read or written per I/O). Jeffareid (talk) 12:20, 21 December 2009 (UTC)
- The short answer to this question is "yes, but the constant of proportionality is very small" (assuming the block size is a constant). However, if the entire list happens to fit in memory this degenerates to O(n) I/O requests. Dcoetzee 03:29, 3 February 2010 (UTC)
Rename or rewrite this article to reflect a proper bottom up merge sort
The initial algorithm and diagram show a top down, divide and conquer approach. When the the definition of merge sort change from the classic Knuth description to the one shown in this ariticle? Note that the wiki article for sorting Sorting_algorithm#Merge_sort includes a proper description of a merge sort (the classic bottom up method). Note that the stable_sort() from Microsoft's standard template library <algorithm> is a bottom up merge sort (it creates a temporary instance of vector to hold the second set of data during the sort process).
A simple description:
Consider a dataset of n records to contain n sorted lists of records each of size 1. These lists are then copied and merged to create a second dataset consisting of n/2 sorted lists of size 2. The lists of size 2 are then copied and merged back into the first dataset to create lists of size 4 and so on, until the list size is the same as the dataset size, in which case that dataset is now sorted. If n is not a power of 2, then the final list of a dataset on each pass will contain fewer records than the other lists.
merging 2 alphabetized files
please even discuss abt mergin 2 alphabetized files —Preceding unsigned comment added by 59.165.185.242 (talk) 17:13, 29 August 2010 (UTC)
Contradiction in the http://en.wikipedia.org/wiki/Mergesort#Merge_sorting_tape_drives
The first two sentences of "Merge sorting tape drives" regarding the little memory demands contradicts the preceding paragraphs that specifically discuss the 2n memory needed for the regular implementation of mergesort —Preceding unsigned comment added by 62.90.139.136 (talk) 15:39, 17 November 2010 (UTC)
External links modified
Hello fellow Wikipedians,
I have just added archive links to one external link on Merge sort. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:
- Added archive http://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java to https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java
When you have finished reviewing my changes, please set the checked parameter below to true to let others know.
This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).
- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—cyberbot IITalk to my owner:Online 12:07, 27 February 2016 (UTC)
External links modified (January 2018)
I have modified the note, leaving a single modified link in it, and made a separate copy below for the other one. --CiaPan (talk) 08:43, 7 February 2018 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Merge sort. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
- Added archive https://www.webcitation.org/6AQdENbYS?url=http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 to http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79
Added{{dead link}}tag to https://openjdk.dev.java.net/source/browse/openjdk/jdk/trunk/jdk/src/share/classes/java/util/Arrays.java?view=markup
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
An editor has reviewed this edit and fixed any errors that were found.
- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—InternetArchiveBot (Report bug) 04:27, 26 January 2018 (UTC)
- I have updated the URL to JDK7 Hg repository commit (Special:Diff/822421084). --CiaPan (talk) 09:00, 26 January 2018 (UTC)
External links modified (January 2018) (2)
This is a copy of the note above for a separate link. --CiaPan (talk) 08:43, 7 February 2018 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Merge sort. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
Added archive https://www.webcitation.org/6AQdENbYS?url=http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 to http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79- Added
{{dead link}}tag to https://openjdk.dev.java.net/source/browse/openjdk/jdk/trunk/jdk/src/share/classes/java/util/Arrays.java?view=markup
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).
- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—InternetArchiveBot (Report bug) 04:27, 26 January 2018 (UTC)
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)
Why is this still on the page? The Java API from Sun clearly states that they use a quicksort? —Preceding unsigned comment added by 99.166.143.138 (talk) 07:36, 22 March 2010 (UTC)
Java 6 and Java 7 use slightly different implementations of Arrays.sort method, but both of them are based on quicksort, not mergesort. From Official Java SE 7 documentation:
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. — Preceding unsigned comment added by Oleh Boiko (talk • contribs) 22:39, 27 March 2011 (UTC)
Also for smaller arrays (with length < 7) Arrays.sort() uses simple insertion sort. This is observable from the Arrays.sort1() method source code. — Preceding unsigned comment added by Oleh Boiko (talk • contribs) 21:09, 28 March 2011 (UTC)
Requesting removal of the following sentence
I think the following sentence does not belong in the article.
Some would argue[who?] that sorting a linked list is not in place because even though you are sorting in the given data structure, the data structure inherently has O(n) extra data you are manipulating (e.g., the links in the list).
The reason for this is that what overhead a datastructure has, has absolutely no impact on the analysis of mergesort -- if anyone think there is grounds for debating whether this is true or not, it should be mentioned in another article specifically devoted to analysis of datastructures and/or the impact they have on algorithms. I would especially considered it to be worth removing as long as no-one is able to give an example of someone who argues this (well). —Preceding unsigned comment added by 80.167.145.223 (talk) 18:26, 2 February 2010 (UTC)
- I agree that this should be removed. What they're trying to say is "using a linked list instead of an array in combination with mergesort doesn't actually save you memory". This is both false (if the objects being sorted are larger than a machine word, it actually does) and pointless (if you really wanted to save memory when sorting small objects, you'd use quicksort). 03:26, 3 February 2010 (UTC)
- I think the sentence is nearly perfect. Suppose that I invent a data structure that contains two arrays (one for the actual data, and another for temporary use). Can I fairly claim that merge sort doesn't require additional memory? Another example: binary tree sort requires O(n) insertions in the tree. Can I claim that it takes O(n) time? Oh well, insertion takes O(log n) time... but this is due to the data structure... we can't blame the algorithm... can we? ;) Seriously: data structures and algorithms are not so independent from each other. --Como (talk) 12:57, 8 February 2010 (UTC)
- Use of much memory used to be a critical question. Now, every kid and housewife has 512 gigabytes of RAM, who cares anymore? Friendly Person (talk) 19:21, 5 May 2011 (UTC)
k-way merge sorting
In my opinion this article is quite restricted in the sense that it only describes two-way merge sorting. k-way merge sorting is somewhat described in the external sorting page, but it would be better off if it were to be included in this article. --EdSchouten (talk) 21:36, 8 March 2011 (UTC)
External merge sort
I just read through this article and the jump to external merge sort using tapes is confusing. I would remove the section or merge it in the External Merge Sort article. Here, this external method is presented without previously explaining what the rationale behind it is.Ltsiros (talk) 18:26, 21 May 2011 (UTC)
39% less comparisons than quicksort's average?
The page currently says: "In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case".
I think the logic behind this is that merge sort's worst case is O(n log n) while quicksort's average is O(1.39n log n). Though this would mean that quick sort does 39% more comparisons than merge sort and merge sort does 28% fewer comparisons than quick sort.
--87.112.168.199 (talk) 02:00, 24 November 2011 (UTC)
introduction and algorithm description
The article introduction uses n without defining n as the number of objects in a list.
The algorithm description should be changed, something like this:
Conceptually, merge sort works as follows:
- Divide the unsorted list into n sublists, each containting 1 object (a list of 1 object can be considered sorted).
- Repeatedly Merge sublists to produce new sublists until there is only 1 sublist remaining. (This will be the sorted list.)
Note that a top down merge sort does not begin any actual merging of data until division of sub-lists result in sub-lists with a size of 1 object, so the above description would apply to both top down and bottom up merge sorts.
The current algorithm descritption includes the statement Sort each sublist recursively by re-applying the merge sort, but the recursive calls to mergesort() only continue to divide sub-lists until sub-list size is 1. Then merge() is used to merge sub-lists as mergesort() returns to previous instances of mergesort(). There's never any actual sorting, only merging of sub-lists.
Sometimes a merge sort will use another sort algorithm to sort relatively small sub-lists:
- Divide the unsorted list into into some number of relatively small sub-lists and sort them using some sorting algorithm.
- Repeatedly Merge sublists to produce new sublists until there is only 1 sublist remaining. (This will be the sorted list.)
I'm not sure if or where this should be mentioned in Merge_sort.
The algorithm description should be reworded. Suggestions welcome.
natural merge sort (again)
Natural merge sort is now only mentioned in the tape sort section. The algorithm description details could be cleaned up a bit, but the psuedocode example needs a redo. I will check to see if there are any other wiki articles that include a natural merge sort to see if the pseudocode can be replaced with a link. Rcgldr (talk) 17:34, 12 January 2012 (UTC)
Added a description to the natural merge section. Rcgldr (talk) 12:06, 13 January 2012 (UTC)
- I removed most of what you added. Natural merges are not done with width arrays. Maintaining such an array can be prohibitive. The NMS compares the current item with the next item in the list to see if it is part of the current run. If it isn't, then that stream is blocked until the current output run finishes. Glrx (talk) 21:01, 17 January 2012 (UTC)
- I should have mentioned both methods. The trade off is element comparson overhead versus sublist size array overhead. In the case of sorting records, the overhead of comparing nearly equal records (no early drop out on the compares) would be greater than the overhead of maintaining an array of sublist sizes. If sorting an array of numbers, then using compare to determine the end of a run can be used instead of a sublist size array. If using compares to determine end of runs, there still needs to be check for end of data (unless some special terminator value can be used), and the sublist array overhead isn't that great if the initial sublist size is reasonably large (32 or greater). However the article as it reads now is OK, and I'm not sure if these type of details are needed. Rcgldr (talk) 09:20, 19 January 2012 (UTC)
merge sort - natural merge sort - use with tape drives
I'm considering removing the pseudocode from the use with tape drives section, since the text added to the Merge_sort#Natural_merge_sort and Merge_sort#Use_with_tape_drives section explain the basic algorithm, and proper pseudocode for a natural merge sort is more complicated than what I would expect for a wiki article. Also I'm not sure how relevant it is to include a lot of text or psuedocode for a legacy tape based sort. Rcgldr (talk) 06:48, 13 January 2012 (UTC)
The use with tape drives section was rewritten. Now that there is pseudocode for the bottom up implementation that is referenced in the tape drive section, the algorithm description in the tape drive section should be adequate. I removed the reference to the ability for tape drives to read and write backwards, since there's a potential issue with running out of tape while trying to write backwards, especially with the natural merge sort variation. Rcgldr (talk) 12:05, 13 January 2012 (UTC)
- There are references to disk drives in Merge_sort#Use_with_tape_drives. It seems a separate sub-section should be created for use with disk drives, or the section title could be changed to use with disk or tape drives. Rcgldr (talk) 09:52, 23 January 2012 (UTC)
About a detail in the pseudo-code
Hi, This is the pseudo-code that is currently on the article.
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
It bothers me that both left and right seem to copy the middle element. Or, if middle goes only to right, then imagine a 2-element array: middle equals 1. Element #1 AND element #2 go to right. Did I understand the code correctly? Or is it ambiguous? Thanks. --Cutter (talk) 00:42, 29 April 2012 (UTC)
Pseudocode Inconsistency
The variety of pseudocode differs from the top-down and bottom-up implementations. Would anyone like to work on updating one of them to match the other? — Preceding unsigned comment added by 173.76.8.60 (talk) 00:26, 6 August 2012 (UTC)
Hybrid Merge Sort
According to Shared Memory, Message Passing, and Hybrid Merge Sorts for Standalone and Clustered SMPs hybrid merge sort is a parallel merge sort using both MPI and OpenMP, i.e., merge sort that runs on clustered SMPs. So far I couldn't find any source for the other definition of hybrid merge sort. It's mostly called "a hybrid of merge sort and ...". — Preceding unsigned comment added by 83N3 (talk • contribs) 20:01, 12 August 2012 (UTC)
- I don't like the top down or so called recursive divide and conquer approaches, since no merging / sorting occurs until the lists are recursively split up into single elements (or perhaps some larger size and sorted conventionally). Might as well start off doing all the divides in a single step by treating a list of n elements as n sorted lists of size 1 (bottom up merge). If there is sufficient memory, a list can be split up into separate "bins" based on the most signficant terms of the comparason portion of elements. For example, with 32 "bins", a list can be seperarated into those 32 "bins" based on the upper 5 bits of the comparason data (like a radix sort). Then 32 independent merge sorts can be performed, one on each bin, using separate processors if available, and then the bins concatenated (no need to do a 32 way merge since the seperation was based on the most significant bits) to produce a sorted list. Even on a single cpu, a hybrid bin / merge sort is significantly faster than a standard merge sort if the data is sufficiently random so that the bins are reasonably close to being equally filled. Rcgldr (talk) 06:07, 30 March 2013 (UTC)
Sort in random
$ echo "Wikibooks Wikipedia Wiktionary" | sort --random-sort Wikipedia Wikibooks Wiktionary
- Unix Sort's algorithm
The sort in GNU/free Linux uses merge sorting which is explained in the Sorting algorithm wiki page.
- new development of Sort
Sort uses merge sorting and is speedy to complete 1 column sorting (in a table of rows and colums of words to be selected and sorted).
There is a new sort(1), headsort(1), using an algorthim with opposite speed properties of merge sort that when sorting more than one column can finish in 1/2 the time, or when only needing to begin streaming the sorted data can finish in 1/2 the time (thus head), and can fork sorting jobs better (though neither does by default): but more often looses to sort's merge when sorting 1 column: it has opposite benefits of merge. Streaming and columns headsort(1) can being streaming in less than 1/2 the time. It's used when use columns and piping data are more often than not used.
If you are interested in headsort(1) "1/2 the time" contact johnandsara2@cox.net or sven_nestle2 on wiki with subject "sort algorithm".
It's good to note that for top speed no algorithm is needed just memory: however quite impractically allot is need for any appreciable task especial where used for random tasks; such a thing is useable only within a single program.
— Preceding unsigned comment added by Sven nestle2 (talk • contribs) 15:21, 1 February 2013
Comparison count: Mergesort vs. Quicksort
The article claims the following: "merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case"
But is that really true? It would seem to me that it isn't. Consider the following array we want to sort:
{0,2,1,3}
In mergesort, merging {0} and {2} into {0,2} takes 1 comparison, and so does merging {1} and {3} into {1,3}. Then merging {0,2} and {1,3} into {0,1,2,3} takes 3 comparisons. So the total amount of comparisons is 5.
In quicksort, if we choose the pivot from the middle (rounding down), the chosen pivot is {2}. It takes 3 comparisons divide the other elements into {0,1} and {3}. {3} is the trivial basecase, but {0,1} needs one more step of recursion and thus 1 comparison. So the total amount of comparisons is 4.
It would seem that quicksort can sometimes beat mergesort in comparison count. Or am I missing something? Does anyone object to removing this seemingly incorrect claim? Ossi (talk) 05:15, 3 March 2013 (UTC)
Algorithm - C code examples
I changed the algorithm section to include C code examples for top down and bottom up implementations, trying to keep the coding style for the two methods as similar as possible, in order to show the actual differences between these two methods. Since the top down algorithm was replaced with a C# version, here is a copy of that section with C code examples in case anyone wants to revert it without having deal with the wiki history of this section. Note LIST.data[] could be an array of anything if a function was added that compares two instances of List.Data elements, such as if( datacompare(&(pleft->data[iL]) , &(pright->data[iR])) ). I chose to use unsigned 64 bit ints to keep the examples simple.
Example C code for top down and bottom up algorithms. Header code common to both examples:
typedef unsigned __int32 U32;
typedef unsigned __int64 U64;
typedef struct _LIST{
U32 size;
U64 data[];
}LIST, *PLIST;
/* soffset(s,m) defines offset to struct s member m */
#define soffset(s, m) ((U32)(((char *)&(((s *)0)->m)) - (char *)0))
#define emptylistsize (soffset(LIST, data[0]))
#define datasize (soffset(LIST, data[1]) - soffset(LIST, data[0]))
#define datacopy(pdst, psrc, count) memcpy(pdst, psrc, (count)*datasize)
PLIST newlist(U32 size)
{
PLIST pnew;
pnew = malloc(emptylistsize + (size*datasize));
pnew->size = size;
return(pnew);
}
Top-down implementation
Example C code for top down merge sort algorithm which uses recursion to divide the list into sublists until sublist size is 1, then merges sublists during returns back up the call chain.
PLIST merge_sort(PLIST plist)
{
PLIST pleft, pright;
/* if size == 1, consider list sorted and return it */
if(1 >= plist->size)
return(plist);
/* else split list into two and recursively call merge_sort() */
/* until list size is 1 */
pleft = newlist(plist->size / 2);
pright = newlist(plist->size - pleft->size);
datacopy(pleft->data, (plist->data), pleft->size);
datacopy(pright->data, (plist->data) + pleft->size, pright->size);
free(plist);
pleft = merge_sort(pleft);
pright = merge_sort(pright);
/* merge the two lists returned from previous iterations of merge_sort() */
return merge_pair(pleft, pright);
}
PLIST merge_pair(PLIST pleft, PLIST pright)
{
PLIST plist;
U32 iL = 0;
U32 iR = 0;
U32 iOut;
/* merge two lists and return a single list */
plist = newlist(pleft->size + pright->size);
for (iOut = 0; iOut < plist->size; iOut++){
if (iL < pleft->size && (iR >= pright->size || pleft->data[iL] <= pright->data[iR]))
plist->data[iOut] = pleft->data[iL++];
else
plist->data[iOut] = pright->data[iR++];
}
free(pleft);
free(pright);
return(plist);
}
Bottom-up implementation
Example C code for bottom up merge sort algorithm which treats the list as an array of n sublists of size 1, and iteratively merges sub-lists back and forth between two list buffers:
static LIST merge_sort(LIST &linp)
{
size_t i, width;
LIST lout(linp.size()); // second list for output
for(width = 1; width < linp.size(); width *= 2){ /* merge pass */
for(i = 0; i < linp.size(); i += 2 * width){ /* merge sublists */
merge_pair(lout, linp, i, min(i+width, linp.size()), min(i+2*width, linp.size()));
}
linp.swap(lout); // swap lists (if optimized would swap ptrs)
}
return(linp); // return sorted list
}
static void merge_pair(LIST &lout, LIST &linp, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;
/* merge a pair of sublists */
for (size_t iout = ileft; iout < iend; iout++){
if (il < iright && (ir >= iend || linp[il] <= linp[ir]))
lout[iout] = linp[il++];
else
lout[iout] = linp[ir++];
}
}
Rcgldr (talk) 00:28, 14 April 2013 (UTC)
- These routines do not appear to use the conventional notion of list processing. The conventional list is not manifest size + vector of elements (essentially equivalent to processing a vector) but rather a linked list of indeterminate size and scattered element allocations. Glrx (talk) 02:33, 14 April 2013 (UTC)
Algorithm - C++ vector code examples
// this typedef would not need to be included in the code examples
typedef vector<int> LIST; // LIST can be a vector of any comparable type
Top-down implementation
static LIST merge_sort(LIST &list)
{
// if size == 1, consider list sorted and return it
if(1 >= list.size())
return(list);
// else split list into two and recursively call merge_sort()
// until list size is 1
LIST::iterator middle = list.begin() + (list.size() / 2);
LIST left(list.begin(), middle); // left = 1st half of list
LIST right(middle, list.end()); // right = 2nd half of list
list.clear(); // optional: clear out the no longer needed list
left = merge_sort(left);
right = merge_sort(right);
// merge the two lists returned from previous iterations of merge_sort()
return(merge_pair(left, right));
}
static LIST merge_pair(LIST &left, LIST &right)
{
size_t il = 0;
size_t ir = 0;
/* merge two lists and return a single list */
LIST list(left.size() + right.size());
for(size_t iout = 0; iout < list.size(); iout++){
if (il < left.size() && (ir >= right.size() || left[il] <= right[ir]))
list[iout] = left[il++];
else
list[iout] = right[ir++];
}
return(list);
}
Bottom-up implementation
static LIST merge_sort(LIST &linp)
{
size_t i, width;
LIST lout(linp.size()); // second list for output
for(width = 1; width < linp.size(); width *= 2){ /* merge pass */
for(i = 0; i < linp.size(); i += 2 * width){ /* merge sublists */
merge_pair(lout, linp, i, min(i+width, linp.size()), min(i+2*width, linp.size()));
}
linp.swap(lout); // swap lists (if optimized would swap ptrs)
}
return(linp); // return sorted list
}
static void merge_pair(LIST &lout, LIST &linp, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;
/* merge a pair of sublists */
for (size_t iout = ileft; iout < iend; iout++){
if (il < iright && (ir >= iend || linp[il] <= linp[ir]))
lout[iout] = linp[il++];
else
lout[iout] = linp[ir++];
}
}
questionable comment in top down implementation, why the change to C#?
This section that was previously written in C so that it would closely match the bottom up implementation, was replaced with a C# example, that isn't as closely matched, and one of the comments is questionable, since it's not clear if the comment is about the recursive call being made or about the list returned from the recursive call.
From Merge_sort#Top-down_implementation in the source fragment
//3/4 Recursively sort both arrays
left = TopDownMergeSort (left);
right = TopDownMergeSort (right);
These calls do not do any sorting, they only recursively divide sub-lists until sub-list size is 1. No actual sorting begins until some instance of TopDownMergeSort() reaches the line that calls the function Merge(). Also the C examples showed that the old list was being freed with a specific call to free(). The C# example doesn't make it clear that the input list(s) is/are being discarded after splitting or merging the input list(s) into new list(s). If more comments are wanted for the C examples to match the comments in the C# example, I'd be happy to update the examples. I could change the C code to C++ code with classes if that would be preferred. Rcgldr (talk) 12:34, 11 April 2013 (UTC)
- I'm not sure I follow your logic a call to TopDownMergeSort definitely sorts the array passed to it. The 'Merge' method is called inside the recursive call. However if this is unclear, we should change it. maju (talk) 01:59, 11 April 2013 (UTC)
- It's understood that the overall result sorts the data. My issue is that the comments in the code should apply to the lines of code in the current instance of TopDownMergeSort(), not to the overall effect of layers of recursion. Those lines of code are just a continuation of the process of dividing a list and recursively calling TopDownMergeSort() until the list size is 1. What needs to be made clear is that until some instance of TopDownMergeSort() reaches the line that calls Merge(), no sorting has taken place, only the splitting of lists, and that no instance of TopDownMergeSort() returns until after a call is made to Merge().
- I have changed the c example to c# because the pointer manipulation and passing sizes obscures the logic. I strongly believe that freeing memory is not part of the algorithm. I you dislike c# as the language we could go for Python or other language, but I will strongly argue with 'native' support for arrays, no pointers and 'automatic' memory management. maju (talk) 01:59, 11 April 2013 (UTC)
- My example did not pass any sizes as parameters. The newlist() function sets the structure size when it's called to create a new list. I could change this to C++ and create a class that has size() as a member instead of using ->size. I don't dislike c#, but I was trying to make it clear that lists were being created and deleted as part of the process, in order to better compare the differences beween top down (many lists being created and deleted), versus bottom up (one list created to be used as a second list, and one list deleted when the sort is completed (the code can be modified so that the original list always ends up with sorted data, but this is an optimization not required for the examples). The other issue is that without using pointers, I'm not sure how you efficiently (no undeed copying of data) implement the bottom up merge sort which swaps the pointers between input and output buffers after each pass. If a proper bottom up merge sort needs pointers, then to be consistent, the top down merge should also use pointers in order to make comparing the different methods easier. Rcgldr (talk) 05:24, 11 April 2013 (UTC)
- Lastly, I see a lot of value in the fact that the c# code deals with anything that can be compared whereas the c code deals only with integers. (talk) 01:59, 11 April 2013 (UTC)
- It's been suggested that the article could have both the C# and C (or C++) examples. I'm not sure it's needed, but it would be better to have both examples written in the same language. My concern about C# is that readers not familiar with C# may wonder why lists are allocated with new but never freed with delete. In addtion, the bottom up implementation is awkward without the use of pointers and swapping them for each pass, since this would require otherwise uneeded copying of data or nearly duplicate code to handle merging back and forth between two lists (which is why I chose C for examples). Rcgldr (talk) 12:34, 11 April 2013 (UTC)
- Comment. The article should not emphasize programming details. WP prefers psuedo code, and a good reason for that is the ideas can be stated without getting mired in the details of a programming language. Glrx (talk) 01:51, 13 April 2013 (UTC)
- Both implementations should be use the same style. This is what I was trying to accomplish with the two C examples, which were very close to wikipedia's C style pseudocode (ignoring the separate header section), so I don't see the problem with what I did. Now the old version is restored, where the top down implementation psuedocode style is very different than the bottom up C example, which what I was trying to resolve. This section should be updated so that both sections use the same style. Rcgldr (talk) 08:28, 13 April 2013 (UTC)
- Comment. I do not see a valid point in reverting back to C/C++ code. C# version is much better to read and it has nice syntax sugars. I did the last changes on C# code and I decided to add generics (similar to templates in C++) today, but now I see you guys already reverted it back. This is an algorithm page and we should show easy-to-understand codes. — Preceding unsigned comment added by 69.18.50.2 (talk) 14:13, 13 April 2013 (UTC)
- Look at the history, I didn't revert it back. My last change was to include both examples. I'm waiting to see a good C# example for bottom up merge sort (post it here on the talk page, that way it won't get undone). Note that outside the class room, most merge sorts are bottom up (or hybrid / bottom up). I added a C++ vector code example for top down merge sort on this talk page if you want to see what that looks like. Rcgldr (talk) 18:44, 13 April 2013 (UTC)
- I was the editor who reverted. I disagree that C# is better to read, and I strongly object to some of that syntactic sugar. WP should not presume that readers are programmers or adept at C or C#. IIRC, there were some edits that replaced explicit variable increments (common in all languages) with the C-family specific ++ idiom / syntactic sugar. I do not see that serving the readers at all. This article is not the place to showcase coding prowess. I also see many of the macro definitions being difficult/opaque for most readers. Glrx (talk) 02:18, 14 April 2013 (UTC)
- Although the intended readers may not be familiar with a specific language, most of them will have some experience with programming. Currently the psuedocode style for top down is not consistent with the C code example for the bottom up. I'd like to see a similar style for both implementations, using the same or similar variable names as needed. If someone wants to fix this, do you have any other issues with language specific idioms other than "++" for incrementing? Are you OK with the usage of pseudo functions like datacopy() instead of for loops and indexing? Rcgldr (talk) 03:35, 14 April 2013 (UTC)
- there were some edits that replaced explicit variable increments (common in all languages) with the C-family specific ++ idiom. Note that the ++ idiom is used in the current bottom up implementation section:
for (j = iLeft; j < iEnd; j++)
- If the issue is mostly the post increments, that could have been easily fixed with a simple edit and adding a couple more lines to the examples, rather than reverting to what there is now, one psuedo code example and one C example, which makes it more difficult to compare the two methods. I didn't want to get in to a debate about C# versus C or C++ examples, I just wanted the top down and bottom up merge implementations to be explained in a similar matter. Rcgldr (talk) 04:54, 22 April 2013 (UTC)
- Except that the current bottom up algorithm is explained using concrete executable C++ code. The suggested C++ code example from above is "simpler" than the current english oriented psuedo-code description which gets into uneeded details such as copying elements one at at time to split a list into two sub-lists. Rcgldr (talk) 09:32, 27 April 2013 (UTC)
- A follow up comment to the mess that currently exists in the examples. The top down example psuedo code gets into unneeded detail in some parts, like a verbose description of splitting a list one element at a time, then later glosses over complex operations like removing the first item from a list with the pseudo macros first(list) and rest(list). The top down example completely ignores the more common top down method of manupulating indexes by recursively generating triplets of indices (left, middle, right) where the range is reduced by 1/2 with each level of recursion, as opposed to the current decription of splitting actual arrays. The bottom up example uses the macro min() without explaing what it does. The top down and bottom up examples should be written in a similar style. The top down example is too english like, too verbose, inconsistent with the level of detail in describing operators. The bottom up example includes a complex if statement that relies on C's "early out" on conditional operators || and && which could be potentially confusing. Rcgldr (talk) 11:18, 25 August 2013 (UTC)
- example of pseudo code for a complex algorithm that uses some high level operators (exponentiation, polynomial multiplication, ..) in an otherwise c like syntax, apparently from a text book: Berlekamp–Massey_algorithm#Berlekamp.E2.80.93Massey_algorithm_for_fields
- Rcgldr (talk) 11:14, 25 August 2013 (UTC)
Is top down merge sort practical?
Top down merge sort uses recursion and splitting / copying of a list until list size is 1, while a bottom up sort just starts off considering a list as n sub-lists of size 1. The overhead for the top down recursion method to just reach what is the starting point for a bottom up merge is quite a bit, the list is split up n-1 times to create n lists of size 1, and the number of elements copied during the splitting phase is log2(n) · n. A top down merge sort also has to allocate and free all of those intermediate lists created during the splitting and merging phases. The end result is that a top down merge takes about 3 times as long as a bottom up merge in a simple case like sorting an array of integers.
It seems that a top down merge sort is mostly a class room exercise. All the merge sorts that I'm aware of in libraries, C++ standard template library, and commercial products, are based on a bottom up merge sort. Rcgldr (talk) 08:32, 13 April 2013 (UTC)
- The top down algorithm provides a divide-and-conquer explanation of the algorithm. Glrx (talk) 02:04, 14 April 2013 (UTC)
- A top down merge sort need not do multiple allocate, copy, free steps. Do not use a poor instance of a program to make a general comment about all instances. A top-down can start by allocating size n work array and then start the recursion. Lexically scoped languages (unlike C) can do that elegantly. The fundamental difference is one of expressing control. In top down, the stack is used to keep track of the subarray being processed. In bottom up, there's one stack frame, but an outside loop and some variables keep track of the current subarray. Glrx (talk) 02:04, 14 April 2013 (UTC)
- Having a secondary work array of n elements doesn't eliminate the extra copy operations. A top down merge sort could use recursion to generate a binary tree of indexes, normally on the stack. Because of the ordering within the binary tree, each merge step has to merge from the orginal array to the work array, then copy the merged output back to the original array, an extra copy step on every merge operation. (Without the copy back after each merge, you'd run into potential situtation where an instance of merge(left, right) would have left on one array and right on the other array, and you'd have to include additional information to keep track of which array each instance of a sub-list was located). I'm not aware of a method to avoid doing this when n is not a power of 2. What is the point of generating a binary tree of indexes and having to do an extra copy step on every merge operation, when these issues are eliminated with an bottom up merge sort? I'm not aware of any standard language library with a merge sort function that uses top down implementation. For example, the HP / Microsoft standard template library for stable_sort() splits up an array into n/32 lists, uses insertion sort to sort each list of 32 (or less) elements, then uses a bottom up merge to complete the sort. Rcgldr (talk) 21:25, 17 April 2013 (UTC)
- Trying to avoid the copy back steps makes a top down merge sort even more complicated. Take the case of a 5 element sublist without the copy back, you end up with an instance of a 2 element sublist on one array and a 3 element sublist on the other array, so one of the sub-lists needs to be copied before the merge can be done. Such an algorithm would have to keep track of which array contains which sub-lists, and when the extra copy steps are needed. All of the examples I've seen of top down done with indexes use a copy back step, such as this one: merge.htm. Recursive implementations are clearly possible, but they introduce uneeded overhead, since the recursion process can be eliminated by simply treating a list of n elements as n sublists of 1 element each (or n/m sublists of m elements each) and iterating as shown in the examples here. Rcgldr (talk) 05:09, 22 April 2013 (UTC)
- That's not the point of this section. The question here was if a top down merge sort is practical (it it is actually used in compiler libraries or commercial products). As an analogy, factorial can be implemented via recursion, but it's not practical (efficient). What's the point of using recursion to split up a list into n sublists of size 1 when a list can be simply considered as n subists of size 1 as the initial state without executing any code? There is the case when a partial top down merge sort can be used to reduce memory overhead, such as allocating a temp buffer 1/2 the size of the data to be sorted, then merging 1/2 of the data at a time (using bottom up merge sort). For the final merge step, you'd have the first half of the data in the temp buffer, and would merge the temp buffer and second half of data into the original data buffer. Rcgldr (talk) 22:44, 27 April 2013 (UTC)
- top down merge sort - indices - which array holds the source depends upon the recursion level parity. Solution for this is to alternate between two almost identical recursive functions, to keep the merge direction in sync with recursion level parity. The top down algorithm section has been updated to show this simple solution. The actual merge process for top down and bottom up is the same. For an index based merge sort, the difference is top down uses recursion to generate triplets of indices (left, middle, right), while bottom up uses iteration. The triplets of indices, (left == start of left run, middle == end of left run == start of right run, right == end of right run) are used for the actual merge process. Both top down and bottom up generate the same set of (n/2 + n/4 + n/8 + ... = n-1) triplets, and only the ordering of the sets used for merging is different. The order of merge operations for top down is top down, depth first, left first, and for bottom up, it's bottom up, breadth first, which may affect cache. Iteration is faster than recursion, but most of the time is spent merging (versus generating triplets) and as mentioned, the merge process is the same for both. Rcgldr (talk) 04:11, 27 August 2013 (UTC)
About a possible O(N*Log(N)) time and only O(1) memory merge sort
i think this is just a variant of some idea of mine block inter blocks insert, basically is about first scanning data, merging using mainly some Euclid arrange routine, performing that block inter block insert... its an old idea of mine but idk if really working neither in these days :) — Preceding unsigned comment added by 93.118.212.93 (talk) 10:52, 8 June 2013 (UTC)
lets say we got two sorted partitions to b merged first we set an index on the first element of first partition assuming we want smallest to largest elements sorting if current element of first group is smaller than current element of second group (initialized as first element of second group) we seek for first partitions next elements till find an element that is bigger than second group current element in this case we switch elements then linearly seek for both of the rite positions in the new places. then kinda repeat this kinda cycle until at least one partition is done case in which(thnx to google translate :) ), if the second partition ended only we might need some Euclid arrange involving second partition and the rest remaining from first partition to linearly O(N) time "switching" their positions... Florin Matei 93.118.212.93 (talk) 16:51, 27 April 2013 (UTC)
u'll have to forgive me im under the effect of my last clopixol shot taken last thurstday, i think that evn possible more sophisticate in order that for really working , this idea of mine its creative and its good enough after all 93.118.212.93 (talk) 17:41, 27 April 2013 (UTC) Florin
Top down implementation
I'm trying to update the top down implementation to use indexing and a style similar to the bottom up implementation, but someone that doesn't even have a wiki page reverted the update. I can make a simpler version of the top down merge that uses a copy step, similar to the current copy step in the bottom up example, to avoid having to alternate between two recursive functions. The top down merge function would be identical to the current bottom up merge function. I can post a proposed example here in this section, but is there any point in doing this? Do the others here involved with this article prefer the text explanation versus any C / C++ example that would be similar in style to the bottom up example? Rcgldr (talk) 23:20, 4 September 2013 (UTC)
Example top down implementation using indices. The copy back can be avoided if the recursion alternates between two functions so that the direction of the merge corresponds with the level of recursion, but this optimization is not required to show how top down merge sort works.
TopDownMergeSort(A[], B[], n)
{
TopDownSplitMerge(A, 0, n, B);
}
TopDownSplitMerge(A[], iBegin, iEnd, B[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// recursively split runs into two halves until run size == 1,
// then merge them and return back up the call chain
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
TopDownSplitMerge(A, iBegin, iMiddle, B); // split / merge left half
TopDownSplitMerge(A, iMiddle, iEnd, B); // split / merge right half
TopDownMerge(A, iBegin, iMiddle, iEnd, B); // merge the two half runs
CopyArray(B, iBegin, iEnd, A); // copy the merged runs back to A
}
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i0 = iBegin, i1 = iMiddle;
// While there are elements in the left or right runs
for (j = iBegin; j < iEnd; j++) {
// If left run head exists and is <= existing right run head.
if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1]))
B[j] = A[i0++]; // Increment i0 after using it as an index.
else
B[j] = A[i1++]; // Increment i1 after using it as an index.
}
}
Rcgldr (talk) 03:19, 5 September 2013 (UTC)
- Oppose switch from lists to arrays. The current version uses lists rather than arrays, so it illustrates a feature of merge sort is that it can be used with sequential sources. I also oppose the use of C idioms such as
i0++outside of for loops. Articles are encouraged to use psuedo code rather than provide detailed implementations. The algorithms should also be simple rather than employing tricks to avoid copying. The goal is to illustrate the basic algorithm. Subtle tricks can be mentioned, but putting them in early obscures the basic algorithm. Glrx (talk) 23:22, 5 September 2013 (UTC)
- lists versus arrays. The same argument could be made for bottom up merge sort as well. Top down merge sort is very inefficient for linked lists since it requires scanning lists to find the mid points, while bottom up implementations avoid this. sequential sources - top down merge sort can not be implemented for true sequential sources such as the classic case of 4 tapes drives (bottom up or polyphase merge sort would be used instead). Perhaps the example posted in this thread could be included between the current top down and bottom up examples, to get an "apples" to "apples" comparason of top down versus bottom algorithms (both using indices on arrays to implement the merge sort). Rcgldr (talk) 01:06, 6 September 2013 (UTC)
- The code here should just be simple pseudocode that illustrates the basic idea well with no tricks. We should have citations in the sections with code in to books or properly checked and supported free software source where readers can find more optimised code - which besides will be more trustworthy than something that is dumped into the free encyclopaedia that anyone can edit. Dmcq (talk) 07:33, 6 September 2013 (UTC)
- The simplest description in the article is the 4 statements in Merge_sort#Use_with_tape_drives. Perhaps that simple description should be moved further up in the article before the top down and bottom up code examples. I'd like to see top down and bottom up code examples implemented in a similar manner so that they can be properly compared. Rcgldr (talk) 01:59, 7 September 2013 (UTC)
bottom up implementation
Some comments about the current bottom up implementation. The parameters "array A[]", and "array B[]" imply that A and B are arrays of arrays. It's ok to note that A[] and B[] are arrays in the comments, but type field could be left blank in the function declarations or use something else to indicate A and B can be of any type. If this was done with a template, you could declare something like template <class element> ... BottomUpMergeSort(int n, element A[], element B[]), but that would probably be more confusing to people not familiar with templates. In the example functions, the ordering of parameters isn't consistent, BottomUpMergeSort() has the size first, source array second, and work array third. BottomUpMerge() has the source array first, 3 indexes next and the destination array last. CopyArray() has the destination array first, the source array second, and the size last. Rcgldr (talk) 02:56, 5 September 2013 (UTC)