Simple QuickSort functions without side-effects in JavaScript and Scala #just-for-fun The tricks to make it "stateless", makes it slower - the algorithm becomes useless, almost, in the context of "quick sort" for large to really large lists. Little optimisation (with filtering & zipping). Then again, it's just for fun....

quicksort-no-side-effects.js

const filterZipWithIndex = (array = [], predicate = () => true) =>
  array.reduce(([arr, index], item) => {
    const current = [item, index];
    const nIndex = index + 1;
    return predicate(current) ? [[...arr, current], nIndex] : [arr, nIndex];
  }, [[], 0])[0];
const unzipIndex = (array = []) => array.map(item => Array.isArray(item) ? item[0] : item);

const partition = (array = [], predicate = () => false) =>
  array.reduce(([left, right], item) =>
               predicate(item)
                 ? [[...left, item], right]
                 : [left, [...right, item]], [[], []]);

function quickSort(arr = []) {
  if (arr.length < 2) return arr;

  const midIndex = Math.floor(arr.length / 2);
  const mid = arr[midIndex];
  const zippedList = filterZipWithIndex(arr, ([_, index]) => index !== midIndex);

  const [lows, highs] = partition(
    zippedList,
    ([num, _]) => num < mid
  );

  return [
    ...quickSort(unzipIndex(lows)),
    mid,
    ...quickSort(unzipIndex(highs))
  ];
}

// You can see a sample usage here: https://codesandbox.io/s/4w4712pj1x

QuickSortNoSideEffect.scala

object QuickSort {
  def sort(list: Seq[Int]): Seq[Int] = {
    if (list.length < 2) list
    else {
      val midIndex = list.length / 2
      val mid = list(midIndex)

      val result = list.zipWithIndex.filter(_._2 != midIndex)
        .partition(n => n._1 < mid)
      result match {
        case (lows, highs) =>
          sort(lows.map(_._1)) ++ Seq(mid) ++ sort(highs.map(_._1))
      }
    }
  }
}