Sorting Algorithm - C#

Here are a couple of ways to pull this off with LINQ, while also correctly sorting the values should they occur in an order other than the one you've presented. For example, if "(avg) Zeta" occurs before "Zeta" then the latter should still come first once sorted.

Here's the sample list, reordered to match what I described above:

var myUnsortedList = new List<string>
{
    "Alpha",
    "(avg) Alpha",
    "(avg) Zeta",
    "Zeta",
    "Beta",
    "(avg) Beta"
};

Lambda syntax

string prefix = "(avg)";
var result = myUnsortedList.Select(s => new
                           {
                               Value = s,
                               Modified = s.Replace(prefix, "").TrimStart(),
                               HasPrefix = s.StartsWith(prefix)
                           })
                           .OrderByDescending(o => o.Modified)
                           .ThenBy(o => o.HasPrefix)
                           .Select(o => o.Value);

Zip / Aggregate

string prefix = "(avg)";
var avg = myUnsortedList.Where(o => o.StartsWith(prefix))
                        .OrderByDescending(o => o);
var regular = myUnsortedList.Where(o => !o.StartsWith(prefix))
                            .OrderByDescending(o => o);
var result = regular.Zip(avg, (f, s) => new { First = f, Second = s })
                    .Aggregate(new List<string>(), (list, o) =>
                                   new List<string>(list) { o.First, o.Second });

Query syntax and string splitting

This one is similar to the lambda syntax, except I'm not using the prefix to determine which string has a prefix. Instead, I am splitting on a space, and if the split result has more than one item then I'm assuming that it has a prefix. Next, I order based on the value and the prefix's availability.

var result = from s in myUnsortedList
             let split = s.Split(' ')
             let hasPrefix = split.Length > 1
             let value = hasPrefix ? split[1] : s
             orderby value descending, hasPrefix
             select s;

Split the lists into two lists, one normal, one average. Sort them both.

Then, do a manual "Zipper Merge".

You should probably create your own custom IComparer<T>:

class MyCustomComparer : IComparer<string>
{
    private readonly StringComparison StringComparer;

    public static readonly MyCustomComparer Ordinal =
        new MyCustomComparer(StringComparison.Ordinal);
    public static readonly MyCustomComparer OrdinalIgnoreCase =
        new MyCustomComparer(StringComparison.OrdinalIgnoreCase);
    // etc.

    private MyCustomComparer(StringComparison stringComparer)
    {
        StringComparer = stringComparer;
    }

    public int Compare(string x, string y)  
    {  
        bool isMatchedX = IsMatchedPattern(x);
        bool isMatchedY = IsMatchedPattern(y);

        if (isMatchedX&& !isMatchedY ) // x matches the pattern.
        {
            return String.Compare(Strip(x), y, StringComparer);
        }
        if (isMatchedY && !isMatchedX) // y matches the pattern.
        {
            return String.Compare(Strip(y), x, StringComparer);
        }

        return String.Compare(x, y, StringComparison.Ordinal);
    }

    private static bool isMatchedPattern(string str)
    {
        // Use some way to return if it matches your pattern.
        // StartsWith, Contains, Regex, etc.
    }

    private static string Strip(string str)
    {
        // Use some way to return the stripped string.
        // Substring, Replace, Regex, etc.
    }
}

Check to see if x and y match your pattern. If neither or both do, then use a standard comparison operation. Basically, you only need the custom comparison operation if one (and only one) matches the pattern.

If x matches the pattern and y doesn't, then strip x and check the stripped version of x against y using the String.Compare(...) operation. If y matches the pattern and x doesn't, then strip y and check the stripped version of y against x using the String.Compare(...) operation.

I updated my answer to show how you can copy the way StringComparison works by exposing static readonly instances of the custom comparer for case/culture options.

Finally, use LINQ with your custom comparer: myList.OrderBy(x => x, MyCustomComparer.Ordinal);

One final note... feel free to optimize this if necessary. This is untested code just off the whim of my mind. The logic is there, I hope. But, typos might have occurred.

Hope that helps.

Another way is to implement an some comparer say MyComparer that implements IComparer<string> and then:

var result = myUnsortedList.OrderBy(x => x, new MyComparer());

I feel like you're using the wrong data structure for this. Why don't you use a SortedDictionary and make it be "name => avg"

untested, probably working code:

SortedDictionary<string, int> dict = new SortedDictionary<string, int>();
dict.Add("Alpha", 10);
dict.Add("Beta", 20);
dict.Add("Zeta", 30);

foreach(string key in dict.Keys.Reverse())
{
   int avg = dict[key];
}

To use Your own logic in linq ordering You should implement Your own Comparer and use it's instance as second parameter in OrderBy or OrderByDescending linq method like below:

namespace ConsoleApplication71
{
    public class AVGComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            // Null checkings are necessary to prevent null refernce exceptions
            if((x == null) && (y == null)) return 0;
            if(x == null) return -1;
            if(y == null) return 1;

            const string avg = @"(avg) ";

            if(x.StartsWith(avg) || y.StartsWith(avg))
            {
                return x.Replace(avg, string.Empty).CompareTo(y.Replace(avg, string.Empty));
            }

            return x.CompareTo(y);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<string> myUnsortedList = new List<string>();

            myUnsortedList.Add("Alpha");
            myUnsortedList.Add("(avg) Alpha");
            myUnsortedList.Add("Zeta");
            myUnsortedList.Add("Beta");
            myUnsortedList.Add("(avg) Beta");
            myUnsortedList.Add("(avg) Zeta");

            var mySortedList = myUnsortedList.OrderByDescending(s => s, new AVGComparer());

            foreach (string s in mySortedList)
            {
                Console.WriteLine(s);
            }
        }
    }
}

The output is:

Zeta
(avg) Zeta
Beta
(avg) Beta
Alpha
(avg) Alpha

In a line:

var sorted = myUnsortedList.OrderByDescending(x => x.Replace("(avg) ", "")).ThenBy(x=> x.Contains("(avg)")).ToList();

Here is a passing test (nunit):

[Test]
public void CustomSort()
{
    var myUnsortedList = new List<string> { "Zeta", "Alpha", "(avg) Alpha", "Beta", "(avg) Beta", "(avg) Zeta" };
    var EXPECTED_RESULT = new List<string> { "Zeta", "(avg) Zeta", "Beta", "(avg) Beta", "Alpha", "(avg) Alpha" };

    var sorted = myUnsortedList.OrderByDescending(x => x.Replace("(avg) ", "")).ThenBy(x=> x.Contains("(avg)")).ToList();

    for (int i = 0; i < myUnsortedList.Count; i++)
    {
        Assert.That(sorted[i], Is.EqualTo(EXPECTED_RESULT[i]));
    }
}