mergeSort(lefthalf)
    mergeSort(righthalf)

    i=0
    j=0
    k=0
    while i<len(lefthalf) and j<len(righthalf):
        if lefthalf[i]<righthalf[j]:
            alist[k]=lefthalf[i]
            i=i+1
        else:
            alist[k]=righthalf[j]
            j=j+1
        k=k+1

    while i<len(lefthalf):
        alist[k]=lefthalf[i]
        i=i+1
        k=k+1

    while j<len(righthalf):
        alist[k]=righthalf[j]
        j=j+1
        k=k+1
print("Merging ",alist)

def quickSortHelper(alist,first,last):
   if first<last:

        splitpoint = partition(alist,first,last)

        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   print("sample",alist)
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp
   print("partition",alist)


   return rightmark

alist = [12,35,67,10,45,29,87,81,34]
quickSort(alist)
print "quick:"
print(alist)

alist = [53,21,93,11,70,31,44,58,27]
bubbleSort(alist)
print "bubbleSort:"
print(alist)

currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print("insertion:")
print(alist)

temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print("selection sort:")
print(alist)

for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      print("After increments of size",sublistcount,
                               "The list is",alist)

      sublistcount = sublistcount // 2
def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55]
shellSort(alist)
print("shell sort")
print(alist)

while not maxLength:
    maxLength = True

    buckets = [list() for _ in range( RADIX )]


    for  i in aList:
      tmp = i / placement
      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False


    a = 0
    for b in range( RADIX ):
      buck = buckets[b]
      for i in buck:
        aList[a] = i
        a += 1


    print("bucket=",buckets,"the list is",alist)
    placement *= RADIX
alist = [54,26,93,17,77,31,44,55]
radixsort(alist)
print("radix")
print(alist)

for val in alist:
        count_alist[val] += 1
        print(count_alist)
    sorted_alist = []
    for i in range(minimum, maximum+1):
        if count_alist[i] > 0:
            for j in range(0, count_alist[i]):
                sorted_alist.append(i)
                print(sorted_alist)
    return sorted_alist

alist = [3,2,-1,1,5,0,10,18,25,25]

print (alist)
print("countingsort=")
print count_sort(alist)