Prolog的插入排序

Question

有一个简单的Prolog插入排序alghoritm：

sorting([A|B], Sorted) :- sorting(B, SortedTail), insert(A, SortedTail, Sorted). 
sorting([], []). 

insert(A, [B|C], [B|D]) :- A @> B, !, insert(A, C, D). 
insert(A, C, [A|C]). 

它确实好于正常的列表：

?- sorting([5, 4, 9, 1, 3, 8], X). 
X = [1, 3, 4, 5, 8, 9]. 

但我也需要对列表进行排序的子表中包含任何人：

?- sorting([2, 5, [5, 4, 3], [6, 3], 4, 8], X). 
X = [2, 4, 5, 8, [5, 4, 3], [6, 3]]. 

现在是什么回报。和

?- sorting([2, 5, [5, 4, 3], [6, 3], 4, 8], X). 
X = [2, 4, 5, 8, [3, 4, 5], [3, 6]]. 

我需要返回。那么我怎样才能对子列表进行排序呢？提前致谢！

Answer 1

通过添加对每个元素进行排序的子例程来找到解决方案。

Answer 2

我提供这个简单的解决方案：

在排序列表

insert(X, [], [X]):- !. 
insert(X, [X1|L1], [X, X1|L1]):- X=<X1, !. 
insert(X, [X1|L1], [X1|L]):- insert(X, L1, L). 

使用圣多美和普林西比插入排序算法插入元素

insertionSort([], []):- !. 
insertionSort([X|L], S):- insertionSort(L, S1), insert(X, S1, S).