1*37da2899SCharles.Forsythimplement Sort; 2*37da2899SCharles.Forsythinclude "sort.m"; 3*37da2899SCharles.Forsyth 4*37da2899SCharles.Forsythsort[S, T](s: S, a: array of T) 5*37da2899SCharles.Forsyth for{ 6*37da2899SCharles.Forsyth S => 7*37da2899SCharles.Forsyth gt: fn(s: self S, x, y: T): int; 8*37da2899SCharles.Forsyth } 9*37da2899SCharles.Forsyth{ 10*37da2899SCharles.Forsyth mergesort(s, a, array[len a] of T); 11*37da2899SCharles.Forsyth} 12*37da2899SCharles.Forsyth 13*37da2899SCharles.Forsythmergesort[S, T](s: S, a, b: array of T) 14*37da2899SCharles.Forsyth for{ 15*37da2899SCharles.Forsyth S => 16*37da2899SCharles.Forsyth gt: fn(s: self S, x, y: T): int; 17*37da2899SCharles.Forsyth } 18*37da2899SCharles.Forsyth{ 19*37da2899SCharles.Forsyth r := len a; 20*37da2899SCharles.Forsyth if (r > 1) { 21*37da2899SCharles.Forsyth m := (r-1)/2 + 1; 22*37da2899SCharles.Forsyth mergesort(s, a[0:m], b[0:m]); 23*37da2899SCharles.Forsyth mergesort(s, a[m:], b[m:]); 24*37da2899SCharles.Forsyth b[0:] = a; 25*37da2899SCharles.Forsyth for ((i, j, k) := (0, m, 0); i < m && j < r; k++) { 26*37da2899SCharles.Forsyth if(s.gt(b[i], b[j])) 27*37da2899SCharles.Forsyth a[k] = b[j++]; 28*37da2899SCharles.Forsyth else 29*37da2899SCharles.Forsyth a[k] = b[i++]; 30*37da2899SCharles.Forsyth } 31*37da2899SCharles.Forsyth if (i < m) 32*37da2899SCharles.Forsyth a[k:] = b[i:m]; 33*37da2899SCharles.Forsyth else if (j < r) 34*37da2899SCharles.Forsyth a[k:] = b[j:r]; 35*37da2899SCharles.Forsyth } 36*37da2899SCharles.Forsyth} 37