Anubis

• (4.5) Quick sorting of lists.*

The proposed sorter uses merge-sort for better space and time efficiency, it is also shorter than the quick-sort version.

define (List($T),List($T)) 
  split_even_odd
    (
      List($T) l,
      List($T) even,
      List($T) odd
    ) =
  if l is
    {
      [ ] then (even,odd),
      [h0 . t0] then 
         if t0 is
           {
             [ ] then ([h0.even],odd),
             [h1 . t1] then split_even_odd(t1,[h0.even],[h1.odd])
           }   
    }.

define List($T)
  merge_sorted
    (
      List($T) l1, 
      List($T) l2,
      ($T,$T) -> Bool less
    ) =
  if l1 is 
    {
      [ ] then l2,
      [h1 . t1] then
        if l2 is
          {
            [ ] then l1,
            [h2 . t2] then
               if less(h1,h2) then [h1.merge_sorted(t1,l2,less)]
               else [h2.merge_sorted(l1,t2,less)]
          }  
    }. 

public define List($T)
  qsort
    (
      List($T) l, 
      ($T,$T) -> Bool less
    ) =
  if l is
    {
      [ ] then [ ],
      [ha . ta] then
        if ta is
          {
            [ ] then [ha],
            [hb . tb] then
              if tb is [] then
                if less(ha,hb) then l else [hb,ha]
              else 
                with w = split_even_odd(l,[],[]),
                if w is (u,v) then
                merge_sorted(qsort(u,less),qsort(v,less),less)
          }
    }.