text: from typing import List
  
  
  def merge_sort(x: List) -> List:
      """Merge sort divides a list into two smaller lists, and recursively repeats the process on the two smaller lists
      till lists of single elements are obtained. These smaller lists are then combined to form a single sorted list of
      the original elements. It has an average time complexity of Θ(nlogn). Time complexity for the worst case is
      O(nlogn). Time complexity for the best case is Ω(nlogn).
  
      >>> merge_sort([4, 2, 3, 1, 0, 5])
      [0, 1, 2, 3, 4, 5]
  
      :param x: list to be sorted
      :return: new sorted list
      """
      length = len(x)
  
      if length <= 1:
          return x
  
      mid_idx = length // 2
      left = merge_sort(x[0:mid_idx])
      right = merge_sort(x[mid_idx:length])
  
      result = []
      while len(left) > 0 and len(right) > 0:
          if left[0] <= right[0]:
              result.append(left.pop(0))
          else:
              result.append(right.pop(0))
      result.extend(left)
      result.extend(right)
  
      return result
  