Merge Sort

Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.

Examples

• {1} is sorted to {1}
• {1, 2, 3} is sorted to {1, 2, 3}
• {3, 2, 1} is sorted to {1, 2, 3}
• {4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}

Corner Cases

• What if the given array is null? In this case, we do not need to do anything.
• What if the given array is of length zero? In this case, we do not need to do anything.

Time Complexity: O(NlogN)

Space Complexity: O(N)　

class Solution(object):
  def mergeSort(self, array):
    """
    input: int[] array
    return: int[]
    """
    # write your solution here
    if array is None or len(array) <= 1:
      return array
    cp_lst = array.copy()
    self.helper(0, len(array) - 1, array, cp_lst)
    return array

  def helper(self, left, right, array, cp_lst):
    if left >= right:
      return
    mid = left + (right - left) // 2
    self.helper(left, mid, array, cp_lst)
    self.helper(mid + 1, right, array, cp_lst)
    self.merge(left, right, mid, array, cp_lst)

  def merge(self, left, right, mid, array, cp_lst):
    for i in range(left, right + 1):
      cp_lst[i] = array[i]
    left_idx = left
    right_idx = mid + 1
    index = left_idx
    while left_idx <= mid and right_idx <= right:
      if cp_lst[left_idx] <= cp_lst[right_idx]:
        array[index] = cp_lst[left_idx]
        left_idx += 1
      else:
        array[index] = cp_lst[right_idx]
        right_idx += 1
      index += 1
    while left_idx <= mid:
      array[index] = cp_lst[left_idx]
      index += 1
      left_idx += 1