Python implementation of Mergesort and Quicksort using Lomuto and Hoare partition.

sorting.py

def merge(D, L, R):
  left_index = 0
  right_index = 0
  for i in range(len(D)):
    if left_index >= len(L):
      D[i] = R[right_index]
      right_index += 1
    elif right_index >= len(R):
      D[i] = L[left_index]
      left_index += 1
    else:
      if L[left_index] < R[right_index]:
        D[i] = L[left_index]
        left_index += 1
      else:
        D[i] = R[right_index]
        right_index += 1
  return D

def mergesort(L):
  if len(L) <= 1:
    return L

  middle_index = len(L) // 2
  left, right = L[:middle_index], L[middle_index:]
  return merge(L, mergesort(left),  mergesort(right))

def lomuto_partition(A, lo, hi):
  pivot = A[hi]
  i = lo - 1
  j = lo
  while j < hi:
    if A[j] < pivot:
      i += 1
      A[i], A[j] = A[j], A[i]
    j += 1
  A[hi], A[i + 1] = A[i + 1], A[hi]
  return i + 1

def _lomutosort(L, lo, hi):
  if lo < hi:
    s = lomuto_partition(L, lo, hi)

    _lomutosort(L, lo, s - 1)
    _lomutosort(L, s + 1, hi)
  return L

def quicksort_lomuto(L):
  return _lomutosort(L, 0, len(L) - 1)

def hoare_partition(A, lo, hi):
  left_index = lo
  pivot_index = hi
  right_index = hi - 1

  while left_index <= right_index:
    while left_index <= right_index and A[left_index] < A[pivot_index]:
      left_index += 1

    while left_index <= right_index and A[right_index] > A[pivot_index]:
      right_index -= 1

    if left_index <= right_index:
      A[left_index], A[right_index] = A[right_index], A[left_index]
      left_index += 1
      right_index -= 1

  A[left_index], A[pivot_index] = A[pivot_index], A[left_index]
  return left_index


def _hoaresort(L, lo, hi):
  if lo < hi:
    s = hoare_partition(L, lo, hi)

    _hoaresort(L, lo, s - 1)
    _hoaresort(L, s + 1, hi)
  return L

def quicksort_hoare(L):
  return _hoaresort(L, 0, len(L) - 1)