Prolog sorting

sort.pl

% Sorting algorithms in prolog for the fun of it

bubble_sort(List, Sorted) :-            % the bubble_sort of List is Sorted only if
    in_order(List) ->                   % List satisfying in_order implies
        List = Sorted                   % List unifies with (is equivalent to) Sorted 
    ;                                   % or
        bubble(List, Bubbled),          % the bubble of List is Bubbled and
        bubble_sort(Bubbled, Sorted).   % bubble_sort of Bubbled is Sorted

in_order([]).                           % empty list satisfies in_order
in_order([_]).                          % list with one element satisfies in_order
in_order([X, Y | L]) :-                 % in_order of list X, Y, followed by L is true only if
    X < Y, in_order([Y | L]).           % X < Y and in_order of list Y followed by L is true

bubble([], []).                         % the bubble of an empty list is an empty list
bubble([X], [X]).                       % the bubble of a single element list is that list
bubble([X, Y | L], Bubbled) :-          % the bubble of X, Y followed by L is Bubbled only if
    Y < X ->                            % Y < X implies
        bubble([X | L], SubBubble),     % the bubble of X followed by L is SubBubbled and
        Bubbled = [Y | SubBubble]       % Bubbled is Y followed by SubBubble
    ;                                   % or
        bubble([Y | L], SubBubble),     % the bubble of Y followed by L is SubBubble and
        Bubbled = [X | SubBubble].      % Bubbled is X followed by SubBubble


selection_sort(List, Sorted) :-
    List = [] ->
        Sorted = []
    ;
        min_rem(List, Min, Rem),
        selection_sort(Rem, RemSorted),
        Sorted = [Min | RemSorted].

min_rem([X | L], Min, Rem) :-
    L = [] ->
        Min = X, Rem = []
    ;
        min_rem(L, X, Min, Rem).

min_rem([], X, X, []).
min_rem([Y | L], X, Min, Rem) :-
    Y < X ->
        min_rem(L, Y, Min, SubRem),
        Rem = [X | SubRem]
    ;
        min_rem(L, X, Min, SubRem),
        Rem = [Y | SubRem].

insertion_sort([], []).
insertion_sort([X | L], Sorted) :-
    insertion_sort(L, [X], Sorted).
insertion_sort([], Sorted, Sorted).
insertion_sort([X | L], Progress, Sorted) :- 
    insert(X, Progress, MoreProgress),
    insertion_sort(L, MoreProgress, Sorted).
insert(X, [], [X]).
insert(X, [Y | L], Inserted) :- 
    Y < X ->
        insert(X, L, SubInserted),
        Inserted = [Y | SubInserted]
    ;
        Inserted = [X, Y | L].

merge_sort([], []).
merge_sort([X], [X]).
merge_sort([X, Y | List], Sorted) :-
    split([X, Y | List], Evens, Odds),
    merge_sort(Evens, SortedEvens),
    merge_sort(Odds, SortedOdds),
    merge(SortedEvens, SortedOdds, Sorted).
split([], [], []).
split([X], [X], []).
split([X, Y | Rem], Evens, Odds) :-
    split(Rem, SubEvens, SubOdds),
    Evens = [X | SubEvens],
    Odds  = [Y | SubOdds].

merge([], [S | Sorted], [S | Sorted]).
merge([S | Sorted], [], [S | Sorted]).
merge([E | Evens], [O | Odds], Merged) :-
    E < O ->
        merge(Evens, [O | Odds], SubMerged),
        Merged = [E | SubMerged]
    ;
        merge([E | Evens], Odds, SubMerged),
        Merged = [O | SubMerged].

quick_sort(List, Sorted) :-
    pivot(List, P) ->
        remove(P, List, Rem),
        partition(Rem, P, Left, Right),
        quick_sort(Left, SortedLeft),
        quick_sort(Right, SortedRight),
        append(SortedLeft, [P | SortedRight], Sorted)
    ;
        List = [], 
        Sorted = [].

remove(P, [X | L], R) :-
    P = X ->
        L = R
    ;
        remove(P, L, RR),
        R = [X | RR].

%% TODO Median of Medians
pivot([P | _], P).

partition([], _, [], []).
partition([X | L], P, Left, Right) :-
    X < P ->
        partition(L, P, SubLeft, Right),
        Left = [X | SubLeft]
    ;
        partition(L, P, Left, SubRight),
        Right = [X | SubRight].