% Figure 9.3  A more efficient implementation of quicksort using difference-pair
% representation for lists. Relation split( X, List, Small, Big) is as defined 
% Figure 9.2.


% quicksort1( List, SortedList): sort List with the quicksort algorithm

quicksort1( List, Sorted)  :-
  quicksort2( List, Sorted - [] ).

% quicksort2( List, SortedDiffList): sort List, result is represented as difference list

quicksort2( [], Z - Z).

quicksort2( [X | Tail], A1 - Z2)  :-
   split( X, Tail, Small, Big),
   quicksort2( Small, A1 - [X | A2] ),
   quicksort2( Big, A2 - Z2).

% recall: concat( A1-Z1,Z1-Z2,A1-Z2), so the concatenation of
% A1-Z1 and [ X|A2]-Z2 is A1-Z2 where Z1=[ X|A2]