Sorting is also known as arranging a list of items in an order either ascending or descending.

Even though worst case time complexity for quick sort is O(n^2), average time complexity is O(n log n).

Worst case for quick sort is reverse sorted list.

Today we will be writing an algorithm for middle element pivot quick sort.

Lets take an array of integers [4,2,1,3,5]

"""
There are two parts
1. finding correct position of the pivot element `partition`
2. sorting the left and right sides of the pivot element `quick_sort`
"""

def partition(array, left, right):
  i = left; j = right; mid = (i + j) // 2
  pivot = array[mid] # pivot <= get middle element
  while i <= j:
    while array[i] < pivot:
      i += 1
    while array[j] > pivot:
      j -= 1
    if i <= j:
      """
      swap the elements if array[i] >= pivot and array[j] <= pivot
      """
      array[i], array[j] = array[j], array[i]
      i += 1
      j -= 1
  return i


def quick_sort(array, left, right):
  p = partition(array, left, right)
  if left < p - 1:
    quick_sort(array, left, p-1)
  if p < right:
    quick_sort(array, p, right)

array = [4,1,5,2,3]
quick_sort(array, 0, 4)
print(array)

"""
Order of execution
left     right   current list    final + 1
0        4       [4, 1, 3, 2, 5]         4
0        3       [1, 4, 3, 2, 5]         1
1        3       [1, 2, 3, 4, 5]         3
1        2       [1, 2, 3, 4, 5]         2
"""