iterative merge

[Søren Kyale]

I tried to make this code readable which probably means it leaves much to be desired there, yet it's better than my usual.

# msort: list -> list

def msort(L):

   """uses merge sort to return a sorted list"""

   if len(L) < 2: return L

   L = simpleDivider(L)

      # split list into a collection of length one lists.

      # being sorted is a property of lenght one lists.

      # Merge sort uses this property to facilitate sorting.

   mergings = len(bin(len(L) - 1).lstrip('0b'))

      # this gives the lenght of the binary string of X (X is len(L)-1)

      # which is the log base 2 of the first power of two 

      # greater than or equal to X. Which is one less than the number

      # of merging cycles required to merge X-1 lists.

   for null in range(mergings + 1):  L = simpleMerger(L)

      # combine lists two at a time merging small

      # ordered lists into larger ordered lists

      # until there is only one ordered list.

   return L[0]    

# simpleDivider: list -> list of lists

def simpleDivider(L):

   """takes an unordered list and returns a list of lenght one

   intrinsicly ordered lists."""

   return [[i] for i in L] 

# simpleMerger(L): list of lists size n -> list of lists size n/2 +1 if n is odd.

def simpleMerger(L):

   """merge ordered lists in a list of lists two by two"""

   half = len(L) >> 1

   for i, iplus in ((i, i + 1) for i in xrange(0, len(L)-1, 2)):

      # replace the bottom half of L with mergers.

      L[i>>1] = mergeTwoLists(L[i], L[iplus])

   

   if len(L) % 2 == 1:       # if L is odd, retain the odd dangling list.

      L[half] = L[-1]

      del L[half+1:]

   else: del L[half:]

   return L

# mergeTwoLists: list, list -> list

def mergeTwoLists(A,B):

   """combine two ordered lists into a single ordered list"""

   (lenA, lenB) = (len(A), len(B))     # tuples can be used to assign registers

   lenC = lenA + lenB

   # A is first, B is second, C is A and B merged.

   C = [0] * lenC

   a, b = 0, 0    # a, b and c are the indexes for A, B and C

   for c in xrange(lenC):

      if a < lenA:                  # if there are still elements in A

         if b == lenB:                 # if B is spent

            C[c:lenC] = A[a:lenA]         # dump A into C and call it a day.

            break

         if A[a] > B[b]:               # otherwise compare waiting elements.

            (C[c], b) = (B[b], b + 1)  # favoring list A because its elements

         else: C[c], a = A[a], a + 1   # were first in the original list.

      else:

         C[c:lenC] = B[b:lenB]   # otherwise A is empty, so dump B into C.

         break

   return C