Categories
interview

Quicksort

Worst Complexity: O(n^2)


const sort = (arr, low, high) => {
  if (low < high) {
    const p = getPartition(arr, low, high);
    sort(arr, low, p);
    sort(arr, p + 1, high);
  }
};

const getPartition = (arr, low, high) => {
  const pivot = arr[low + Math.floor((high - low) / 2)];
  low--;
  high++;
  while (true) {
    do {
      low++;
    } while (arr[low] < pivot)
    do {
      high--;
    } while (arr[high] > pivot)
    if (low >= high)
      return high;
    const temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
  }
};

const inp = [4, 3, 2, 1];
sort(inp, 0, inp.length - 1);
console.log(inp); // [1, 2, 3, 4]

Demo