text: class MergeSort:
      """
      Sorting is done by comparing the smallest elements of each half. 
      The first element of each list are the first to be compared. 
      If the first half begins with a smaller value, then we add that to the sorted list. 
      We then compare the second smallest value of the first half with the first smallest value of the second half.
      """
  
  def merge(left_list, right_list):
      sorted_list = []
      left_list_index = right_list_index = 0
  
      left_list_length, right_list_length = len(left_list), len(right_list)
  
      for _ in range(left_list_length + right_list_length):
          if left_list_index < left_list_length and right_list_index < right_list_length:
              if left_list[left_list_index] <= right_list[right_list_index]:
                  sorted_list.append(left_list[left_list_index])
                  left_list_index += 1
              else:
                  sorted_list.append(right_list[right_list_index])
                  right_list_index += 1
  
          elif left_list_index == left_list_length:
              sorted_list.append(right_list[right_list_index])
              right_list_index += 1
  
          elif right_list_index == right_list_length:
              sorted_list.append(left_list[left_list_index])
              left_list_index += 1
  
      return sorted_list
  
  
  def merge_sort(nums):
      if len(nums) <= 1:
          return nums
  
      mid = len(nums) // 2
  
      left_list = merge_sort(nums[:mid])
      right_list = merge_sort(nums[mid:])
  
      return merge(left_list, right_list)
  