Skip to content

Instantly share code, notes, and snippets.

@chris-taylor

chris-taylor/golfsort.hs

Last active January 4, 2016 19:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chris-taylor/8668743 to your computer and use it in GitHub Desktop.
Save chris-taylor/8668743 to your computer and use it in GitHub Desktop.
Download ZIP
Golf'd mergesort
Raw
golfsort.hs
sortBy c=m.map(:[]) -- O(n log n)
where m[]=[];m[x]=x;m x=m(n x);n[]=[];n[x]=[x];n(x:y:z)=p x y:n z
p[]y=y;p x[]=x;p (w:x)(y:z)=case c w y of GT->y:p(w:x)z;_->w:p x(y:z)
sort x=m(map(:[])x)
where m[]=[];m[x]=x;m x=m(n x);n[]=[];n[x]=[x];n(x:y:z)=p x y:n z
p[]y=y;p x[]=x;p (w:x)(y:z)=if w>y then y:p(w:x)z else w:p x(y:z)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment