Merge sort implemented in the nix programming language

demo

nix-repl> sort = import ./mergesort.nix

nix-repl> sort [ 3 1 2 8 0 2 3 5 ]      
[ 0 1 2 2 3 3 5 8 ]

mergesort.nix

let re = func: func func; in
re (
sort: input:
  with builtins;
  let
    zip = re (zip: l1: l2: 
      if length l1 == 0 then
        l2
      else if length l2 == 0 then
        l1
      else
        if head l1 < head l2 then
          [ (head l1) ] ++ zip zip (tail l1) l2
        else
          [ (head l2) ] ++ zip zip l1 (tail l2)
    );
    skip = re (skip: l: n:
      if n == 0 then
        l
      else
        skip skip (tail l) (n - 1)
    );
    take = re (take: l: n: 
      if n == 0 then
        []
      else 
        [ (head l) ] ++ take take (tail l) (n - 1)
    );
  in
  if length input <= 1 then
    input
  else
    zip
      (sort sort (take input (length input / 2)))
      (sort sort (skip input (length input / 2)))
)