Quick Sort

Begin with an array arr.

1. Pick a pivot index. Often at the end of the array. or find using a median of three algorithm
2. Declare two indices j and i; and a temporary variable temp
   • j is at the start of the array
   • i is one less than the beginning of the array
3. Do while j < pivot:
   1. If arr[j] < arr[pivot]:
      • i++
      • swap arr[i] and arr[j] using temp variable
        • assign temp = arr[i]
        • assign arr[i] = arr[j]
        • assign arr[j] = temp
   2. j++
4. Now j = i. So i++.
5. Swap arr[i] and arr[j]. Set pivot = i.
   • Now the arr[pivot] is in the right spot. i.e. all items left of pivot are less than the pivot and all items greater than the pivot are greater than the pivot.
6. Finally, recursively return quicksort(arr[:pivot - 1]) + [arr[pivot]] + quicksort(arr[pivot + 1:])