InsertionSort.cool

// This code snippet's origin is [a paper](https://www.lume.ufrgs.br/bitstream/handle/10183/151038/001009883.pdf)
// from [LUME - the Digital Repository of the Universidade Federal do Rio Grande do Sul](https://www.lume.ufrgs.br/apresentacao)
class List() {
    def isNil() : Boolean = abort();
    def head() : Int = abort();
    def tail() : List = abort();
}
    
class Nil() extends List() {
    override def isNil() : Boolean = true;
}
        
class Cons(var car : Int, var cdr : List) extends List() {
    override def isNil() : Boolean = false;
    override def head() : Int = car;
    override def tail() : List = cdr;
}

class Main() extends IO() {
    def insert(lst : List, i : Int) : List = {
        // out_string("Main.insert: i = "); out_int(i); out_nl();
        if (lst.isNil()) {
            // out_string("Main.insert: lst.isNil()"); out_nl();
            new Cons(i, lst)
        }
        else if (i <= lst.head()) {
            // out_string("Main.insert: i <= "); out_int(lst.head()); out_nl();
            new Cons(i, lst)
        }
        else {
            // out_string("Main.insert: else"); out_nl();
            new Cons(lst.head(), insert(lst.tail(), i))
        }
    };
    
    def sort(lst : List) : List = {
        // out_string("Main.sort"); out_nl();
        if (lst.isNil()) {
            // out_string("Main.sort: lst.isNil()"); out_nl();
            lst
        }
        else {
            // out_string("Main.sort: else"); out_nl();
            insert(sort(lst.tail()), lst.head())
        }
    };

    def out_list(lst : List) : Unit = {
        if (lst.isNil())
            out_nl()
        else {
            out_int(lst.head());
            out_string(" ");
            out_list(lst.tail())
        }
    };
        
    {
        var lst : List = new Cons(30, 
            new Cons(20, 
                new Cons(50, 
                    new Cons(40, 
                        new Cons(10, new Nil())))));

        out_list(lst);
        out_list(sort(lst))
    };
}

// DIAG: Build succeeded: Errors: 0. Warnings: 0
// OUT: 30 20 50 40 10
// OUT: 10 20 30 40 50