Talk:Merge 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 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).

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.