quick-sort-loop.ts

/*
[[5, 3, 8, 1, 2, 4, 9, 7, 6, 5, 3, 0]]
[[3, 1, 2, 4, 3, 0], 5, [8, 9, 7, 6, 5]]
[[1, 2, 0], 3, [4, 3], 5, [7, 6, 5], 8, [9]]
[[0], 1, [2], 3, [3], 4, 5, [5, 6], 7, 8, 9]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9]
*/
function quickSort(array: number[]) {
  const stack: (number[]|number)[][] = [[array]];
  let target: (number[]|number)[];
  let pivot: number;
  let noArray = true;
  while (target = stack.shift()) {
    noArray = true;
    const newStackItem: (number[]|number)[] = [];
    for (let i = 0; i < target.length; i++) {
      const item = target[i];
      if (!Array.isArray(item)) {
        newStackItem.push(item);
        continue;
      }

      pivot = item.shift(); // first pivot
      if (!item.length) {
        newStackItem.push(pivot);
        continue;
      }
      noArray = false;

      const left: number[] = [];
      const right: number[] = [];
      for (const n of item) {
        if (n < pivot) left.push(n);
        else right.push(n);
      }
      if (left.length) newStackItem.push(left);
      newStackItem.push(pivot);
      if (right.length) newStackItem.push(right);
    }
    if (noArray) return newStackItem;
    stack.push(newStackItem);
  }
}

const quickSortedArray = quickSort(Array.from(Array(100000), () => Math.floor(Math.random() * 100000)));
console.log('quickSortedArray', quickSortedArray);