Talk:Merge sort

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)

I have to ask why you're saying merge sort can't be implemented without temporary arrays. There is a "C code" section below here which shows exactly this -- how to implement merge sort without any temporary arrays.--Manixrock (talk) 12:44, 17 April 2010 (UTC)

You mean apart from temp1 and temp2? Oli Filth^{(talk|contribs)} 13:27, 17 April 2010 (UTC)

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 θ(n²) 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). 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)

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)

Natural Mergesort

This type of merge sort I read about first in 'Scheme and the Art of Programming', George Springer and Daniel P. Friedman.
They call it a natural mergesort.

Here is a first stab (in python) at a bottom up , inplace merge sort:

def count_sorted( items, start=0 ):
  for x in range(start+1,len(items)):
    if items[x-1]>items[x]:
      return x - start ;
  return len(items) - start ;

def reinsert( items, val, start, end ):
  for x in range( start, end-1 ):
    if items[x+1] > val :
      items[x] = val
      return
    else:
      items[x] = items[x+1]
  items[end-1] = val


def merge_sublists( items, left, right ):
  for x in range(0,left):
    if items[x] > items[left]:
      val = items[x]
      items[x] = items[left]
      reinsert( items, val, left, left+right )

def merge( items ):
  left= count_sorted(items)
  while left < len(items):
    right = count_sorted( items, left )
    merge_sublists( items, left, right )
    left = left + right

A possible optimization is that when the longest ordered sublist is one, find the longest reverse ordered list and reverse it.

-David Medlock, Jan 13, 2006

Is that timsort? --Damian Yerrick (talk | stalk) 17:45, 19 December 2011 (UTC)

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)

Smart compilers will turn / 2 into a SAR -- no need for an extra >>> operator. [ -j.engelh (talk) 15:07, 22 November 2007 (UTC) ]

Agreed that section doesn't belong; removing it.Kbk (talk) 19:01, 17 December 2007 (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)

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:

1. "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!"
2. "Pity they gave me this big array to sort; hmm, how can I get 2 sorted arrays from that?"
3. "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"
4. "Hmm, who can I ask to sort the halves?"
5. "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 $\Theta(n \log (n))$, but the natural variant is only $O(n \log (n))$, since it takes just $O(n)$ when the data are already sorted. The infobox should say $O(n \log (n))$, 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.

Jeffareid (talk) 12:52, 21 December 2009 (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)

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)

In a tape merge sort, the 2n memory refers to the tape memory. The small memory requirement refers to memory requirements on the processor. The processor memory is small because it only needs to hold the next item of each merge list. Glrx (talk) 16:51, 17 November 2010 (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)

The source of the algorithm in question

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)

A primary reference is not required. Knuth is WP:RS and the statement should be WP:V. If you are claiming that Knuth does not say von Neumann invented the algorithm in 1945, then that would be a WP:V attack. It does not sound like that is your dispute; instead you merely want a document with a 1945 date. That is not a WP requirement for a citation. Glrx (talk) 20:30, 12 April 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:

1. Divide the unsorted list into n sublists, each containting 1 object (a list of 1 object can be considered sorted).
2. 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:

1. Divide the unsorted list into into some number of relatively small sub-lists and sort them using some sorting algorithm.
2. 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.

Rcgldr (talk) 06:21, 10 January 2012 (UTC)

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)