'''sort.py

   Jed Yang, 2016-10-30

   A few basic sorting algorithms.
'''

def selection_sort(array):
   '''Sort by SELECTING the min and swapping it into its correct place.'''
   n = len(array)
   for i in range(n):
      minIndex = i
      for j in range(i+1, n):
         if array[j] < array[minIndex]:
            minIndex = j
      array[i], array[minIndex] = array[minIndex], array[i]
   return array

def insertion_sort(array):
   '''Sort by INSERTING the next element into a sorted prefix.'''
   n = len(array)
   for i in range(1, n):
      j = i
      while j > 0 and array[j] < array[j-1]:
         array[j], array[j-1] = array[j-1], array[j]
         j = j-1
   return array

def bubble_sort(array):
   '''Sort by swapping adjacent pairs that are inverted.'''
   n = len(array)
   for i in range(n):
      for j in range(n-1):
         if array[j] > array[j+1]:
            array[j], array[j+1] = array[j+1], array[j]
   return array

def merge_sort(array):
   '''Sort by MERGING recursively sorted halves.'''
   n = len(array)
   if n == 1:
      return array
   middle = n // 2
   left = merge_sort(array[:middle])
   right = merge_sort(array[middle:])
   return merge(left, right)

def merge(listA, listB):
   '''Merges two sorted lists into one sorted list.'''
   a = 0
   b = 0
   listC = []
   while a < len(listA) and b < len(listB):
      if listA[a] < listB[b]:
         listC.append(listA[a])
         a = a + 1
      else:
         listC.append(listB[b])
         b = b + 1
   # one of listA or listB is exahusted, so precisely one loop below will run
   while a < len(listA):
      listC.append(listA[a])
      a = a + 1
   while b < len(listB):
      listC.append(listB[b])
      b = b + 1
   return listC

array = [3, 4, 1, 7, 2, 2, 3]
print(array)
print(selection_sort(array))
print(insertion_sort(array))
print(bubble_sort(array))
print(merge_sort(array))