% http://www.swi-prolog.org/pldoc/man?section=lists

% Import basic list functionality
:- use_module(library(lists)).

% These lists wont work, why not?
append([40,7,9,8],[1],list).
append([1],[3,5],l2).


ssort(L,LS) :-
    ssortStartLoop(L,LS).

% Need to start the loop and append to an _empty_ list
% Input list L, output list LS
ssortStartLoop(L,LS) :-
    lowestFirst(L,L1),
    L1 = [H|T],
    append([],H,SortedTemp),
    ssortRecursive(T,SortedTemp,LS).

% Put the lowest element first, rest unordered
% Input list L, output list L1
lowestFirst(L,L1) :-
    findLowest(L,Lowest),
    addRest(Lowest,L,L1).

% Finds the lowest value Lowest from input list L
findLowest(L,Lowest) :-
    L = [H|T],
    loopListLowest([H|T],Lowest).

% Different variants of looping over the list
% Input X is the lowest enountered value so far
% Tail is the elements that are not checked yet

% X is lowest, include X in next iteration
loopListLowest([X|Tail],Lowest) :-
    Tail = [H|T],
    X < H,
    loopListLowest([X|T],Lowest).

% H is lowest (or the same), include H in next iteration
loopListLowest([X|Tail],Lowest) :-
    Tail = [H|T],
    X >= H,
    loopListLowest([H|T],Lowest).

% No more elements to check (tail is empty)
% X is the lowest value
loopListLowest([X|[]],Lowest) :-
    Lowest = X.


% Remove Lowest from the list, and add it as the first element
addRest(Lowest,L,L1) :-
    select(Lowest,L,RestOfL),
    append([Lowest],RestOfL,L1).


%
ssortRecursive(L,SortedTemp,LS) :-
    is_list(SortedTemp),
    lowestFirst(L,L1),
    L1 = [H|T],
    append(SortedTemp,[H],SortedTemp2),
    ssortRecursive(T,SortedTemp2,LS).

ssortRecursive(L,SortedTemp,LS) :-
    integer(SortedTemp),
    lowestFirst(L,L1),
    L1 = [H|T],
    append([SortedTemp],[H],SortedTemp2),
    ssortRecursive(T,SortedTemp2,LS).

ssortRecursive([],SortedTemp,LS) :-
    LS = SortedTemp.