BackgroundThis is a problem from a programming contest. The Sharonians of planet Sharon, at the far end of our galaxy, have  discovered various samples of English text from our electronic  transmissions, but they did not find the order of our alphabet. Being  a very organized and orderly species, they want to have a way of  ordering words, even in the strange symbols of English. Hence they  must determine their own order.For instance, if they agree on the alphabetical order:  UVWXYZNOPQRSTHIJKLMABCDEFGThen the following words would be in sorted order based on the above alphabet order:WHATEVER ZONEHOWHOWEVERHILLANYANTLERCOWThe input format is:<N - number of words> <alphabet order><0>..<N>What I DidI intended to use List<T>.Sort and use a custom Comparator so I don't have to implement a sorting algorithm from scratch. However, the alphabet input and the order is case insensitive and since List<T>.Sort uses an unstable QuickSort, words like go and Go would be swapped.My workaround is so dirty but it works by making a copy of the word list to serve as a look-up to preserve the order of equal words.The Code As Isusing System;using System.Collections.Generic;class Program{    static void Main(string[] args)    {        List<string> words = new List<string>();        List<string> wordsCopy = new List<string>();        string firstLine = Console.ReadLine();        //assume correct input        int numOfWords = int.Parse(firstLine.Split( .ToCharArray())[0]);        string alphabet = firstLine.Split( .ToCharArray())[1].ToUpper();        for (int i = 1; i <= numOfWords; i++)        {            words.Add(Console.ReadLine());            wordsCopy.Add(words[words.Count - 1]);//preserve index        }        Console.WriteLine();        //Quicksort is unstable (meaning equal elements will still be swapped, e.g. go and Go)        words.Sort(delegate(String x, String y)        {            int max = (x.Length > y.Length) ? y.Length : x.Length;            if (x.ToUpper().Equals(y.ToUpper()))            {                //dirty work-around to stablize the sort                return wordsCopy.IndexOf(x) < wordsCopy.IndexOf(y) ? -1 : 1;            }            for (int i = 0; i < max; i++)            {                int indexX = alphabet.IndexOf(x[i].ToString(), StringComparison.InvariantCultureIgnoreCase);                int indexY = alphabet.IndexOf(y[i].ToString(), StringComparison.InvariantCultureIgnoreCase);                if (indexX > indexY)                {                    return 1;                }                else if (indexX < indexY)                {                    return -1;                }            }            return 0;        });        Console.Write(String.Join(\n, words));        Console.ReadLine();    }}This code was good enough to win, but what could I have done better?
Stable custom alphabetical order using List.Sort
c#;optimization;sorting;contest problem
First of all, I would take advantage of the fact that the other commonly used implementation of sorting in .Net is stable: the OrderBy() extension method from LINQ. Though it requires IComparer interface for custom sorting, it won't accept the Comparer delegate you're using.If you wanted to keep using List.Sort(), then I think your implementation is mostly okay, with the following caveats:It has the potential to balloon the time complexity of the sort from \$\mathcal{O}(n \log n)\$ to \$\mathcal{O}(n^2 \log n)\$. This is becuse every call to your comparison delegate can take \$\mathcal{O}(n)\$ time, due to the calls to IndexOf().It doesn't work correctly if some words in the list repeat themselves. For example Good, good, Good would be sorted as Good, Good, good.Neither of these might matter to you, but I think it's good to be aware of them.Your comparison doesn't work correctly for pairs where one word is the start of another (like HOW and HOWEVER from the sample list), it returns 0 for those, even though the words are not the same.Some small specific comments about your code:All your code is inside a single method. That's usually frowned upon, but I think it's probably okay when you have this little code. The same goes for separation of concerns.int numOfWords = int.Parse(firstLine.Split( .ToCharArray())[0]);string alphabet = firstLine.Split( .ToCharArray())[1].ToUpper();I would avoid the repetition of firstLine.Split( .ToCharArray()) by extracting its result to a separate variable.Also, you don't actually need that ToCharArray(), since Split() is a params method.string[] firstLineParts = firstLine.Split(' ');int numOfWords = int.Parse(firstLineParts[0]);string alphabet = firstLineParts[1].ToUpper();wordsCopy.Add(words[words.Count - 1]);I think creating wordsCopy would be simpler if you used the constructor of List that can copy existing collection:List<string> wordsCopy = new List<string>(words);words.Sort(delegate(String x, String y)You can use the lambda syntax here. That way, you don't have to (but can, if you want) specify the types of parameters:words.Sort((x, y) =>x.ToUpper().Equals(y.ToUpper())ToUpper() is culture-specific, which can cause problems in some cultures (particularly Turkish).But you probably don't need to care about that if you only ever expect to run this program on your computer.