Quick Sort

Quick sort is a Divide & Conquer algorithm. At each step, it finds the Pivot and then makes sure that all the smaller elements are left of Pivot and all larger elements are on the right. It continues to do so recursively until the entire array is sorted. Unlike Merge Sort, it doesn’t requires any external space.

Code algorithm

Let’s now look at how to implement it in code.

function quickSort(arr: number[], start: number, end: number): void {
    if (start >= end) return;
    const pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  };
}

function partition(arr: number[], p: number, q: number): number {
  const pivot = q;
  let i = p - 1;
  for (let j = p; j <= q; ++j) {
    if (arr[j] > arr[pivot]) continue;
    ++i;
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  return i;
};

For time and space complexity, check out my post on Run Time Complexity.