package jazz.lang;

///////////////////////////////////////////////////////////////////////////////
//
//                              Comparable types
//
///////////////////////////////////////////////////////////////////////////////

public interface Comparable {
  public static sort<T: Comparable>(v: T[]): T[];
}

///////////////////////////////////////////////////////////////////////////////
//
//                               Implementation
//
///////////////////////////////////////////////////////////////////////////////

// Merge sort implementation of the "sort" function
Comparable.sort<T>(v) = sort(v.length)(v): T[v.length] {

  fun sort(n)(v) = v'
  {
    if (n < 2) {
      v' = v;
    } else {
      m = n div 2;
      v' = merge(m)(sort(m)(v))(n-m)(sort(n-m)(v[m..n-1]));
    }
  }
  
  fun merge(n1)(v1)(n2)(v2) = v
  {
    if (n1 == 0) {
      v = v2;
    } else if (n2 == 0) {
      v = v1;
    } else if (v1[0] < v2[0]) {
      v[0] = v1[0];
      v[1..] = merge(n1-1)(v1[1..])(n2)(v2);
    } else {
      v[0] = v2[0];
      v[1..] = merge(n1)(v1)(n2-1)(v2[1..]);
    }
  }
}