Prolog で QuckSort

Prolog で QuickSort．

% qsort(L1, L2) : L1 をソートすると L2 になる

qsort([], []).

qsort([P|L], L2) :-

	partition(L, P, [X, Y]),

	qsort(X, L3),

	qsort(Y, L4),

	append(L3, [P|L4], L2).
% partition(L, P, [X, Y]) : L をピボット P で分割すると X と Y に分かれる

partition([], _, [[],[]]).

partition([A|L], P, [[A|X], Y]) :-

	A < P,

	partition(L, P, [X, Y]).

partition([A|L], P, [X, [A|Y]]) :-

	A >= P,

	partition(L, P, [X, Y]).

実行結果．

?- qsort([3,6,2,4,8,1], X).
X = [1, 2, 3, 4, 6, 8] 
Yes

?- 

憶えたてなのでカットの使いどころが分からない．

partition([], _, [[],[]]).

partition([A|L], P, [[A|X], Y]) :-

	A < P,

	partition(L, P, [X, Y]),

	!.

partition([A|L], P, [X, [A|Y]]) :-

	partition(L, P, [X, Y]).

でもいいような気がするけど本当だろうか．
勉強が必要．