'''
   20211021
   
   Robin Dawes
   
   Merge Sort
'''



def merge(list_1, list_2):
   '''returns a new list containing the sorted elements of list_1 and list_2
     
     list_1 and list_2 must be sorted already
     
     Merge the two lists by repeatedly choosing the smallest value available,
     which must be either the smallest value remaining in list_1 or the smallest
     value remaining in list_2
   '''

   merged_list = []
   f1, f2 = 0, 0
   l1, l2 = len(list_1) - 1, len(list_2) - 1
   # loop until one list is used up
   while f1 <= l1  and  f2 <= l2:
      if list_1[f1] <= list_2[f2]:              #compare the smallest values in the two lists
         merged_list.append(list_1[f1])
         f1 += 1
      else:
         merged_list.append(list_2[f2])
         f2 += 1

   # one of the lists is now used up but the other still has values to be
   # copied to the new list
   if f1 > l1:
      merged_list.extend(list_2[f2:])
   else:
      merged_list.extend(list_1[f1:])
      
   return merged_list


def merge_sort(a_list):
   '''initiates the recursive merge sort
      a_list must be a list of objects that can be compared and ordered
   '''
   return merge_sort_rec(a_list, 0, len(a_list)-1)
   
   
def merge_sort_rec(a_list, first, last):
   '''returns a new list containing the elements from a_list[first] to a_list[last]
     in sorted order
     
     Parameters:
          a_list - a list of comparable objects or values
          first - a numeric value indicating the start of the part of a_list to be sorted
          last - a numeric value indicating the end of the part of a_list to be sorted
   '''
   if first > last:
      return []
   elif first == last:
      return [a_list[first]]
   else:
      mid = (first + last) // 2
      left = merge_sort_rec(a_list, first, mid)
      right = merge_sort_rec(a_list, mid+1, last)
      return merge(left, right)
   
   
   
# main   
   
import random

# create a list of random integers
values = random.sample(range(1, 100), 20)
print("\n")
print(values, "\n")
print(merge_sort(values), "\n")
print(values, "\n")                       # showing that the original list is unaffected