merge-sort-loop.ts

function mergeSort(array) {
  const stack = [...array].map(n => [n]);

  while (1) {
    const nextStackItem = [];
    const left = stack.shift();
    const right = stack.shift();
    
    let leftIndex = 0, rightIndex = 0;
    if (left.length === array.length) {
      return left;
    }

    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        nextStackItem.push(left[leftIndex]);
        leftIndex++;
      } else {
        nextStackItem.push(right[rightIndex]);
        rightIndex++;
      }
    }
    nextStackItem.push(...left.slice(leftIndex), ...right.slice(rightIndex));
    stack.push(nextStackItem);
  }
}

mergeSort(Array.from(Array(100), () => Math.floor(Math.random() * 100)));