class List
{ public int item; public List rest; public List(int item, List rest) { this.item = item; this.rest = rest; } // helper methods for quicksort public static List Append(List xs, List ys) { if (xs == null) return ys; else return new List(xs.item, Append(xs.rest, ys)); } public static List Filter(Func<int,bool> p, List xs) { if (xs == null) return null; else if (p(xs.item)) return new List(xs.item, Filter(p, xs.rest)); else return Filter(p, xs.rest); } public static List QSort(List xs) { if (xs == null) return null; else { int pivot = xs.item; List less = QSort(Filter(x => x <= pivot, xs.rest)); List more = QSort(Filter(x => x > pivot, xs.rest)); return Append(less, new List(pivot, more)); } } // Helper methods for mergesort public static int Length(List xs) { if (xs == null) return 0; else return 1 + Length(xs.rest); } public static List Take(int n, List xs) { if (n == 0) return null; else return new List(xs.item, Take(n - 1, xs.rest)); } public static List Drop(int n, List xs) { if (n == 0) return xs; else return Drop(n - 1, xs.rest); } public static List Merge(List xs, List ys) { if (xs == null) return ys; else if (ys == null) return xs; else if (xs.item <= ys.item) return new List(xs.item, Merge(xs.rest, ys)); else return new List(ys.item, Merge(xs, ys.rest)); } public static List MSort(List xs) { if (Length(xs) <= 1) return xs; else { int len = Length(xs) / 2; List left = MSort(Take(len, xs)); List right = MSort(Drop(len, xs)); return Merge(left, right); } } public static string Show(List xs) { if(xs == null) return ""; else return xs.item.ToString() + " " + Show(xs.rest); }
}