History of Merge sort

 def merge(array, start1, end1, start2, end2, output, outstart, cmp):
     """Merge two sorted sequences into a new sorted sequence.
 
     Takes two sorted sequences 'array[start1:end1]' and
     'array[start2:end2]' and merges them into a new sorted sequence,
     which it places in the array 'output', starting at 'outstart'.
 
     """
     while start1 != end1 or start2 != end2:
         if start2 == end2 or (start1 != end1 and
                               not cmp(array[start1], array[start2])):
             output[outstart] = array[start1]
             start1 = start1 + 1
         else:
             output[outstart] = array[start2]
             start2 = start2 + 1
         outstart = outstart + 1
 
 def mergesort(array, cmp=lambda x, y: x > y, scratch=None, start=None,
               end=None):
     """The fastest stable sort for large data sets."""
     if scratch is None: scratch = [0] * len(array)
     if start is None: start = 0
     if end is None: end = len(array)
     if end - start > 1:
         middle = (start + end) / 2
         mergesort(array, cmp, scratch, start, middle)
         mergesort(array, cmp, scratch, middle, end)
         merge(array, start, middle, middle, end, scratch, start, cmp)
         array[start:end] = scratch[start:end]