Stable custom alphabetical order using List.Sort Background


  This 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:
  UVWXYZNOPQRSTHIJKLMABCDEFG
  
  Then the following words would be in sorted order based on the above alphabet order:


WHATEVER 
ZONE
HOW
HOWEVER
HILL
ANY
ANTLER
COW


The input format is:

&lt;N - number of words&gt; &lt;alphabet order&gt;
&lt;0&gt;
..
&lt;N&gt;




What I Did

I intended to use List&lt;T&gt;.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&lt;T&gt;.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 Is

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        List&lt;string&gt; words = new List&lt;string&gt;();
        List&lt;string&gt; wordsCopy = new List&lt;string&gt;();

        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 &lt;= 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 &gt; y.Length) ? y.Length : x.Length;

            if (x.ToUpper().Equals(y.ToUpper()))
            {
                //dirty work-around to stablize the sort
                return wordsCopy.IndexOf(x) &lt; wordsCopy.IndexOf(y) ? -1 : 1;
            }

            for (int i = 0; i &lt; max; i++)
            {
                int indexX = alphabet.IndexOf(x[i].ToString(), StringComparison.InvariantCultureIgnoreCase);
                int indexY = alphabet.IndexOf(y[i].ToString(), StringComparison.InvariantCultureIgnoreCase);

                if (indexX &gt; indexY)
                {
                    return 1;
                }
                else if (indexX &lt; 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?
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&lt;string&gt; wordsCopy = new List&lt;string&gt;(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) =&gt;




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.