Quicksort in Prolog


quicksort divides the list by choosing (arbitrary) the first element, called a pivot, and using this element to split the list into Left and Right.  Left has all elements smaller than the pivot.  Right has all elements larger than the pivot.  The sorted list is [Left, pivot, Right].  

quicksort([X|Xs],Ys) :-
  partition(Xs,X,Left,Right),
  quicksort(Left,Ls),
  quicksort(Right,Rs),
  append(Ls,[X|Rs],Ys).
quicksort([],[]).

partition([X|Xs],Y,[X|Ls],Rs) :-
  X <= Y, partition(Xs,Y,Ls,Rs).
partition([X|Xs],Y,Ls,[X|Rs]) :-
  X > Y, partition(Xs,Y,Ls,Rs).
partition([],Y,[],[]).

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

Explanation

quicksort(Xs,Ys)  sorts list Xs into ascending order list Ys. (or Ys is an ordered permutation of Xs).

Ys is a sorted [X|Xs] where Left and Right is a result of partitioning Xs by X, Ls and Rs are the sorted Left and Right recursively, and Ys is the result of appending [X|Rs] to Ls.

partitioning [X|Xs] with Y gives list Ls (left) and Rs (right), if X is less than or equal Y and partitioning Xs with Y gives Ls and Rs.  

The base case is the empty list.

Wow, this is beautiful.