-module(quicksort).
-export([sort/1]).

% A program that sorts a list using quicksort.  Quicksort works by 
% splitting the list up into two parts according to a pivot value.  One
% part contains all elements whose value is higher than the pivot value,
% and the other part contains all elements whose values are lower.  These 
% two parts are then recursively sorted and are joined with the pivot in 
% the middle to produce a sorted list

sort([]) -> [];
sort([Pivot|Rest]) ->
	% split list
	{Higher, Lower} = partition(Pivot, Rest),
	% recursively sort and stick together
	lists:append(sort(Lower), [Pivot|sort(Higher)]).	

% entry point for partition function
partition(Pivot, L) -> partition(Pivot, L, {[],[]}).	

% go through list and put higher values into the first list of the tuple, and
% lower (or equal) values into the second
partition(Pivot, [], {High, Low}) -> {High, Low};
partition(Pivot, [H|T], {High, Low}) when H > Pivot ->
	partition(Pivot, T, {[H|High], Low});
partition(Pivot, [H|T], {High, Low}) when H =< Pivot ->
        partition(Pivot, T, {High, [H|Low]}).