Merge Sort Example

mergeSort.py

def mergeSort(arr):
  def combine(L, R):
    i = j = k = 0
  
    while i < len(L) and j < len(R):
      if L[i] < R[j]:
        arr[k] = L[i]
        i += 1
      else:
        arr[k] = R[j]
        j += 1
      k += 1
  
    while i < len(L):
      arr[k] = L[i]
      i += 1
      k += 1
    while j < len(R):
      arr[k] = R[j]
      j += 1
      k += 1
      
  # base case (already sorted!)
  if len(arr) == 1:
    return arr

  # Step 1: Split
  mid = len(arr) // 2
  L = arr[:mid]
  R = arr[mid:]

  # Step 2: Sort halves recursively
  mergeSort(L)
  mergeSort(R)

  # Step 3: Combine halves
  combine(L, R)
  return arr


lst = [38, 27, 43, 3, 9, 82, 10]
print(mergeSort(lst))

Condensed version

def mergeSort(arr):
  def combine(L, R):
    # omitted implementation
      
  # base case (already sorted!)
  if len(arr) == 1:
    return arr

  # Step 1: Split
  mid = len(arr) // 2
  L = arr[:mid]
  R = arr[mid:]

  # Step 2: Sort halves recursively
  mergeSort(L)
  mergeSort(R)

  # Step 3: Combine halves
  combine(L, R)
  return arr