Stable custom alphabetical order using List<T>.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:

 

..

What I Did

I intended to use List.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.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 words = new List();
List wordsCopy = new List();

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

if (x.ToUpper().Equals(y.ToUpper()))
{
//dirty work-around to stablize the sort
return wordsCopy.IndexOf(x) indexY)
{
return 1;
}
else if (indexX < indexY)
{
return -1;
}
}

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 wordsCopy = new List(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.

StackExchange Code Review Q#49127, answer score: 6