quick-sort-in-place-loop.ts

function quickSortinPlace(array: number[]) {
  const stack: [number, number][] = [[0, array.length - 1]];
  let target: [number, number];
  let temp: number;
  while (target = stack.shift()) {
    const [firstIndex, lastIndex] = target;

    const middleIndex = Math.floor((firstIndex + lastIndex) / 2);

    const pivot = array[middleIndex];
    let leftIndex = firstIndex;
    let rightIndex = lastIndex;

    while (leftIndex <= rightIndex) {
      while (pivot > array[leftIndex]) leftIndex++;
      while (pivot < array[rightIndex]) rightIndex--;

      if (leftIndex >= rightIndex) break;
      temp = array[leftIndex];
      array[leftIndex] = array[rightIndex];
      array[rightIndex] = temp;
      leftIndex++;
      rightIndex--;
    }
    const nextMiddleIndex = leftIndex - 1;
    if (nextMiddleIndex - firstIndex > 1) stack.push([firstIndex, nextMiddleIndex]);
    if (lastIndex - leftIndex > 1) stack.push([leftIndex, lastIndex]);
  }
  return array;
}
      
console.log(quickSortinPlace(Array.from(Array(100000), () => Math.floor(Math.random() * 100000))));