LinkedList Sorting

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);
    }
}

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);
    }
}

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);
    }
}