ShuffleSort

/* ShuffleSort, as seen on xkcd #1185 "Ineffective Sorts"
 * Author: Alex Burgess
 */

using System;
using System.Collections.Generic;
using System.Linq;

namespace ShuffleSort
{
    static class Program
    {
        static void Main(string[] args)
        {
            List<String> theList;
            if (args.Length > 0)
            {
                theList = args.ToList<String>();
            }
            else
            {
                Console.WriteLine("Please enter some arguments next time.");
                theList = new List<string>();
                theList.Add("e");
                theList.Add("c");
                theList.Add("a");
                theList.Add("b");
                theList.Add("d");
            }
            List<String> theUnsortedList = new List<string>();
            theList.ForEach((item) =>
            {
                theUnsortedList.Add((string)item.Clone());
            });

            Console.Write("Your original list: ");
            theList.PrintList();

            DateTime normalSortStart = DateTime.Now;
            theUnsortedList.Sort();
            DateTime normalSortFinish = DateTime.Now;
            TimeSpan normalSortTimeTaken = normalSortFinish.Subtract(normalSortStart);
            Console.WriteLine("It took {0} seconds and {1} milliseconds to sort using List.Sort() (i.e. normally)", normalSortTimeTaken.Seconds, normalSortTimeTaken.Milliseconds);

            Console.WriteLine("Sorting the list by shuffling...");
            Console.WriteLine();

            DateTime startTime = DateTime.Now;
            UInt64 count = 0;

            while (!IsSorted(theList))
            {
                theList.Shuffle();
                count++;
            }

            DateTime finishTime = DateTime.Now;
            Console.Write("Your sorted list:   ");
            theList.PrintList();
            TimeSpan timeTaken = finishTime.Subtract(startTime);
            Console.WriteLine("It took {0} hours, {1} minutes, {2} seconds and {3} milliseconds to sort.", timeTaken.Hours, timeTaken.Minutes, timeTaken.Seconds, timeTaken.Milliseconds);
            Console.WriteLine("There were {0:n0} lists generated before the list was sorted.", count);



#if DEBUG
            Console.WriteLine("Press any key to exit.");
            Console.ReadKey();      //prevent console from closing in Visual Studio after debugging
#endif
            }

        static void PrintList<String>(this List<String> list)
        {
            for (int i = 0; i < list.Count - 1; i++)
            {
                Console.Write(list[i] + ",");
            }
            Console.WriteLine(list[list.Count - 1]);
        }


        static void Shuffle<String>(this List<String> list)
        {
            Random rand = new Random();
            int n = list.Count;
            while (n > 1)
            {
                n--;
                int k = rand.Next(n + 1);
                String value = list[k];
                list[k] = list[n];
                list[n] = value;
            }
        }

        static bool IsSorted(List<String> list)
        {
            for (int i = 1; i < list.Count; i++)
            {
                String current = list[i];
                String previous = list[i-1];
                if (String.Compare(current, previous, true) < 0)        //is value greater than the previous one?
                {
                    return false;           //no - list is not sorted
                }
            }
            return true;                    //could not find a counterexample so list must be sorted
        }
    }
}