归并排序法与快速排序法
归并排序法与快速排序法的思想中都有分治的成分，一般用到了递归，因而这两种排序算法用prolog实现还是比较自然的
归并排序法
采用2分归并，每次把表分为等长的两部分，分别对其进行排序，再将结果合并——于是涉及到表的分割(split)、合并(merge)
split(array H,array T,array R)将表H等分为T和R
merge(array H,array T,array R)则将表H和T合并为R，与append不同的是合并是按元素大小顺序的
msort(array H,array T)将表H排序成为表T，则：
msort([],[]). % 对空表的处理
msort([X],[X]). % 单个元素的处理
msort([X,Y|H],T):- % 两个以上元素的处理
split([X,Y|H],L,R),
msort(L,SL),
msort(R,SR),
merge(SL,SR,T).
即可完成排序。
split用到了另一个谓词splitby(integer N,array H,array L,array
R)即将表H的前N的元素分到表，剩下的分到R中。
split(H,L,R):-
S = size(H) div 2, % 一半
splitby(S,H,L,R).
splitby(0,X,[],X). % 特殊情况的处理
splitby(N,[X|H],[X|L],R):-
N ＞ 0,
N1 = N - 1,
splitby(N1,H,L,R).
现在可以把表分开了！
merge实际上是排序的核心
merge([],R,R).
merge(L,[],L).
merge([X|L],[Y|R],[X|T]):-
X ＜= Y,
merge(L,[Y|R],T).
merge([X|L],[Y|R],[Y|T]):-
X ＞ Y,
merge([X|L],R,T).
现在可以排序了
msort([4,3,2,1],X),write(X),nl,readln(Q).
快速排序法
也是分治策略，对于待排序的表，把它以某一元素X谓标准，分成小于（等于）X、大于X两部分，设谓词为partition(element X,array
H,array L,array R)将表H依X分成表L和表R，则
qsort([],[]).
qsort([X],[X]).
qsort([X|H],T):-
partition(X,[X|H],L,R),
qsort(L,SL),
qsort(R,SR),
append(SL,SR,T).
下面讨论partition
partition(X,[],[],[]).
partition(X,[Y|H],[Y|L],R):- % 小于（等于）X的元素放入表L
Y ＜= X,
partition(X,H,L,R).
partition(X,[Y|H],L,[Y|R]):- % 大于X的元素放入表R
Y ＞ X,
partition(X,H,L,R).
测试一下：
qsort([4,56,1,3,67],X),write(X),readln(Q).
