Skip to content

Python Simple Sort

Quick sort routine...

def sort(array):
  if len(array) <= 1: return array
  mid = len(array) // 2
  return merge (sort(array[0:mid]), sort(array[mid:]))

# this may not be the most thoroughly idiomatic python, or the
# most efficient merge (it duplicates data when "Transmitting")
# but it works
def merge(left, right):
    merged = []

    i = 0
    j = 0
    while(len(merged) < len(left)+len(right)):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
            if i == len(left):
                # Knuth, TaoCP Vol 3 5.2.4 Calls this the "transmit"       
                y = right[j:]
                for x in y:
                    merged.append(x)
                break
        else:
            merged.append(right[j])
            j += 1
            if j == len(right):
                y = left[i:]
                for x in y:
                    merged.append(x)
                break

    return merged

a=[1,3,2,4]
b=sort(a)
print b
Published inPython