QuickSort

using System;
using System.Linq;
using System.IO;

namespace QuickSort
{
    /// <summary>
    /// Algorithms: Design and Analysis by Tim Roughgarden
    /// Part 1, Programming Question - 2
    /// </summary>
    /// <see>
    /// https://class.coursera.org/algo-007/quiz?quiz_type=homework
    /// </see>
    class Program
    {
        static void Main(string[] args)
        {
            var input = File.ReadLines(args[0]).Select(int.Parse);
            Console.WriteLine(new Program((_, l, r) => l).Run(input.ToArray()));
            Console.WriteLine(new Program((_, l, r) => r - 1).Run(input.ToArray()));
            Console.WriteLine(new Program(GetMedianOfThree).Run(input.ToArray()));
        }

        static int GetMedianOfThree(int[] a, int l, int r)
        {
            var m = l + (r - l - 1) / 2;
            if ((a[l] < a[m] && a[m] < a[r - 1]) ||
                (a[l] > a[m] && a[m] > a[r - 1]))
            {
                return m;
            }

            if ((a[m] < a[l] && a[l] < a[r - 1]) ||
                (a[m] > a[l] && a[l] > a[r - 1]))
            {
                return l;
            }

            return r - 1;
        }

        public Program(Func<int[], int, int, int> choosePivotFunc)
        {
            _choosePivot = choosePivotFunc;
        }

        public int Run(int[] a)
        {
            return Run(a, 0, a.Length);
        }

        private int Run(int[] a, int l, int r)
        {
            if (l >= r)
            {
                return 0;
            }

            var i = Partition(a, l, r);
            return Run(a, l, i) + Run(a, i + 1, r) + r - l - 1;
        }

        private int Partition(int[] a, int l, int r)
        {
            Swap(a, l, _choosePivot(a, l, r));

            var p = a[l];
            var i = l + 1;
            for (var j = l + 1; j < r; j++)
            {
                if (a[j] < p)
                {
                    Swap(a, i, j);
                    i++;
                }
            }

            Swap(a, l, i - 1);
            return i - 1;
        }

        private static void Swap(int[] a, int i, int j)
        {
            if (i == j)
            {
                return;
            }

            var temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }

        private readonly Func<int[], int, int, int> _choosePivot;
    }
}