Haskell-inspired quick sort in ES6

quicksort.hs

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<=x) xs)  
        biggerSorted = quicksort (filter (>x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted

quicksort.js

/* 
1) passing array
   > quicksort([4,3,2,1]); // => [1,2,3,4]
*/
function quicksort(tail) {
  if (tail.length === 0) return [];
  let head = tail.splice(0, 1)[0];
  return quicksort(tail.filter( _ => _ <= head))
         .concat([head])
         .concat(quicksort(tail.filter( _ => _ > head )))
}

/* 
2) via arguments
   > quicksort(4,3,2,1); // => [1,2,3,4]
   or:
   > quicksort(...[4,3,2,1]); // => [1,2,3,4]
*/
function quicksort(x, ...xs) {
  if (arguments.length === 0) return [];
  return quicksort(...xs.filter( _ => _ <= x))
         .concat([x])
         .concat(quicksort(...xs.filter( _ => _ > x )))
}

For a second I thought you were using a left arrow. Lol

Why don't use destruction in array version as well? function quicksort([x, ...xs]) {...}

I wonder if there are performance implications when using the spread operator with larger arrays to pass into quicksort the two sub lists.

I like this one :)

const quicksort = array => {
    if (array.length === 0) return [];
    let [x, ...xs] = array;    
    return [
        ...quicksort(xs.filter(y => y < x)),
        x,
        ...quicksort(xs.filter(y => y >= x))
    ];
};

So concise and beautiful!

Yeah, why the hell would you waste your time typing out "array.sort((a, b) => a - b);" only to get back 25,384x the run speed? Seriously, cute but useless.

Here is mine:

const qsort = ([pivot, ...tail]) =>
    tail.length ?
        [...qsort(tail.filter(x=>x<pivot)),
         pivot,
         ...qsort(tail.filter(x=>x>=pivot))]
    : !isNaN(pivot) ? 
        [pivot]
    :
        []

I don't know how I should feel about this one, but I like the fact that you can almost read it like "pattern matching".

And for anyone wondering: yes, using the spread operator results in a performance drop.

[...Array(100000)].map(Math.random).sort((a, b) => a-b)

runs in 127ms.

qsort([...Array(100000)].map(Math.random))

runs in 479ms.

Using concat instead of [...before, pivot, ...after] brings it down to 367ms.

And, finally, using

const qsortnd = array => {
    const head = array[0], tail = array.slice(1)
    return array.length ?
        qsortnd(tail.filter(x=>x<array[0]))
        .concat(head)
        .concat(qsortnd(tail.filter(x=>x>=array[0])))
    : 
        []
}

instead makes it run in 275ms.

@AntoineMurat

In your qsort "pattern matching" lookalike -

const qsort = ([pivot, ...tail]) =>
    tail.length
      ? // then ...
      : // else..

You could use default arguments to your advantage -

const None =
  Symbol ()

const qsort = ([ pivot = None, ...tail ]) =>
  pivot === None
    ? // then ...
    : // else ...

---

In qsortnd , you call tail.filter twice per element in the array resulting in many wasted cycles. Using reduce we can collapse the two loops into just one -

const append = (x, xs = []) =>
  xs .concat ([ x ])

const partition = (p, xs = []) =>
  xs .reduce
    ( ([ t, f ], x) =>
        p (x)
          ? [ append (x, t), f ]
          : [ t, append (x, f) ]
    , [ [], [] ]
    )

const [ left, right ] =
  partition
    ( x => x < 3
    , [ 6, 2, 1, 4, 5, 3 ] 
    )

console .log (left, right)
// [ 2, 1 ]
// [ 6, 4, 5, 3 ]

---

Both qsort and qsortnd can overflow the stack for large arrays. Can you think of a way around this? (Hint: it can still be recursive! and fast!)

I like this one :)

const quicksort = array => {
    if (array.length === 0) return [];
    let [x, ...xs] = array;    
    return [
        ...quicksort(xs.filter(y => y < x)),
        x,
        ...quicksort(xs.filter(y => y >= x))
    ];
};

One issue is performance since you are filtering the same array twice

function quickSort(values = []) {
  const [pivot, ...restValues] = values;
  
  if (!pivot) return [];
  if (!restValues.length) return [pivot];
  
  const [lesser, greater] = restValues.reduce((partitions, val) => {    
    partitions[+(val > pivot)].push(val);

    return partitions;
  }, [[], []]);
  
  return [
    ...quickSort(lesser),
    pivot,
    ...quickSort(greater),
  ];
}