def insertion_sort(old_list):
  n=len(old_list)
  k=0
  for i in range(1,n):
    temp=old_list[i]
    j=i
    while j>0 and temp<old_list[j-1]:
      old_list[j]=old_list[j-1]
      j=j-1
    old_list[j]=temp
  return old_list

def bubble_sort(old_list):
  n=len(old_list)
  for i in range(n-1):
    for j in range(n-1-i):
      if old_list[j]>old_list[j+1]:
        old_list[j],old_list[j+1]=old_list[j+1],old_list[j]
  return old_list

def quick_sort(list,low,high):
  i=low
  j=high  
  if i >= j:
    return list
  key=list[i]
  while i < j:
    while i < j and list[j]>=key:
      j = j - 1
    list[i]=list[j]
    while i < j and list[i]<=key:
      i = i + 1
    list[j]=list[i]
  list[i]=key
  quick_sort(list,low,i-1)
  quick_sort(list,j+1,high)
  return list

def select_sort(list):
  length=len(list)
  for i in range(length):
    min_index=i
    for j in range(i,length):
      if list[j]<list[min_index]:
        min_index=j
    list[i],list[min_index]=list[min_index],list[i]
  return list

def merge_sort(list):
  if len(list)<=1:
    return list
  mid=int(len(list)/2)
  left=merge_sort(list[:mid])
  right=merge_sort(list[mid:])
  return merge(left,right)
def merge(list1,list2):
  list=[]
  i,j=0,0
  while i<len(list1) and j<len(list2):
    if list1[i]<list2[j]:
      list.append(list1[i])
      i=i+1
    elif list1[i]>=list2[j]:
      list.append(list2[j])
      j=j+1
  list.extend(list1[i:])
  list.extend(list2[j:])
  return list

def shell_sort(nums):
  step = len(nums)/2
  while step > 0:
    for i in range(step, len(nums)):
      while i >= step and nums[i-step] > nums[i]:
        nums[i], nums[i-step] = nums[i-step], nums[i]
        i -= step
    step = step/2
  return nums