Silly sorting algorithms in C

Algorithms and data structures are fundamental building blocks of informatics and are usually one of the first classes at university that you must take, to become a certified professional. It rarely involves any fun, but that doesn’t have to be the case. In this article I want to show you a few “funny” and “silly” algorithms, that are not useful in real world situations but nevertheless sow the funny side of the subject.

Silly sorting algorithms

But what exactly makes them silly? I call them silly because they are so inefficient or so obscure that the real-world use case for them is negligible.

Some seriousness

Before I dive into the fun part, firstly some seriousness. The algorithms that I will show are implemented in C# and use C# specifics where possible, however the core principles, as in most of the algorithms are not language bound.

A few algorithms involve checking the dataset, whether they are sorted or not . This is performed by the IsSorted method, which is essentially a linear search:

static bool IsSorted<T>(IList<T> values, IComparer<T> comparer)
{
    for (int i = 1; i < values.Count; i++)
    {
        if (comparer.Compare(values[i - 1], values[i]) > 0)
        {
            return false;
        }
    }
    return true;
}

Where possible I used generics, the IComparer<T> interface and where it was not possible I used Generic Math interfaces. If you are interested in this topic, then you can find details in this excellent article by Viktor Ponamarev: Generic Math in .NET: Design, Constraints, and Practical Use or the .NET documentation: https://learn.microsoft.com/en-us/dotnet/standard/generics/math

Bogo sort

Bogo sort is also known as permutation sort or in some cases stupid sort or monkey sort. The core principle behind this algorithm is the generate and test paradigm. It randomly generates permutations of the input until it finds one that is sorted. Usually, this algorithm is part of the curriculum in data structures and algorithms, because even if it sounds like a bad idea, in the best case it has Ω(n) complexity and in worst case it has O(1), which is the best achivable. However the average performance Θ(n × n!) makes it unusable in any serious situation.

static void BogoSort<T>(IList<T> values, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    Random random = new Random();
    while (!IsSorted(values, comparer))
    {
        // shuffle the array
        for (int i = 0; i < values.Count; i++)
        {
            int j = random.Next(i, values.Count);
            (values[i], values[j]) = (values[j], values[i]);
        }
    }
}

Serveral variations of this algorithm exist, like the Bogobogosort which is a recursive implementation of this algorithm, but my favorite one is the Quantum variant, which is fortunately just hypotethical. This variant of the algorithm generates a random permutation of its input using a quantum source of entropy andchecks if the list is sorted. If it’s not, then it destroys the universe. It assumes that the many worlds interpretation of quantum mechanics holds, the use of this algorithm will result in at least one surviving universe, where the input was sorted in O(n) time.

Mirracle sort

Aslo based on the generate and test paradigm, miracle sort relies on an external event, like a mirracle or divine intervention. The algorithm algorithm continuously checks whether the input is sorted. If it’s not, then it repeats this step over and over agin untill, the input for some reason becomes sorted.

Sounds silly, but it could work under the right conditions. Cosmic rays can affect computer memory chips and ocasionally flip one bit at a time, so in theory it could work. The best Ω(n) complexity and the worst case O(1) limits still hold, but realisticly we are speaking of Θ(∞) runtime.

static void MirracleSort<T>(IList<T> values, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    while (!IsSorted(values, comparer))
    {
        // wait for miracle to happen, solar bitflip or divine intervention
    }

    //Array is now sorted
}

Sleep sort

Sleep sort is one of my favorite obscure sorting algorithms, because in C# it can nicely demonstrate how to work with tasks and some caches, that are not trivial. It works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item’s sort key, then emits the item. Items are then collected sequentially in time.

I think the most fascinating part of this algorithm is that it works, because it essentially offloads the sorting work to the task scheduler of the operating system.

static void SleepSort(IList<int> values)
{
    for (int i=0; i<values.Count; i++)
    {
        int n = values[i]; //copy needed here because of closure
        Task.Run(async () =>
        {
            await Task.Delay(n * 1);
            Console.WriteLine(n);
        });
    }
}

Purge sort aka. Stalin sort

So far, we looked at algorithms that somewhat work and are not lossy, meaning that they keep the original contents of the array. However, this is not true for the following algorithm, that is called Purge sort or sometimes Stalin sort. The key idea behind this algorithm is that it iterates through the elements and checks whether they are in order or not. If an element found that isn’t order it simply removes it or in other words, as Mr. Stalin did it, sends it to the Gulag. The fascinating part of this algorithm is that it always has an O(n) performance, but you may lose a lot of data in the process.

static void StalinSort<T>(IList<T> values, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;

    int i = 0;
    while (i < values.Count - 1)
    {
        if (comparer.Compare(values[i], values[i + 1]) > 0)
            values.RemoveAt(i + 1);
        else
            i++;
    }
}

The C# specific catch here is that the IList<T> implementation must support the RemoveAt method, so a regular array won’t work with this implementation. An alternative would be to return an array, with the approved items.

Thanos sort

Continuing the list with another algorithm named after a person, I present you Thanos sort, which simply deletes randomly half of the input dataset and calls it a day. The resulting dataset might not be sorted after the operation but remember: “The hardest choices require the strongest wills”

static void ThanosSort<T>(List<T> items)
{
    int toDelete = items.Count / 2;
    Random r = new Random();
    int deleted = 0;
    while (deleted < toDelete)
    {
        int index = r.Next(0, items.Count); //Perfectly balanced, as all things should be
        items.RemoveAt(index);
        deleted++;
    }
}

Genghis Khan sort

The Genghis Khan sort deletes all elements, except for the first and then repopulates the dataset with the successors of the first element. Similarly to it’s name giver it forces order by destroying the existing structure.

static void GenghisKhanSort<T>(IList<T> values) 
    where T: IIncrementOperators<T>
{
    T item = values[0];
    for (int i= 1; i < values.Count;i++)
    {
        values[i] = ++item;
    }
}

KGB / Orwell sort

The next algorithm has no official name as far as I know, but I like to call it KGB sort, but it can be called any name that reflects the intent and the intent is that we assume that the elements are sorted and there is no need for additional sorting. If anyone tries to sort, we simply return the original array and call it a day or you can simply throw an exception, since asking questions, like the “Is the array sorted?” might be dangerous to the security of the state.

static void KgbSort<T>(IList<T> values, IComparer<T>? comparer = null, [CallerMemberName] string? caller = null)
{
    ReportCallerAsSuspicious(caller);
}

static void ReportCallerAsSuspicious(string? caller)
{
    //Log the caller as suspicious or take appropriate action
}

A C# specific here is the CallerMemberName attribute, which automatically fills in the caller methods name into the caller argument.

Communist/Marxist sort

Some blogposts mix up the terminology and sometimes refer to the Stalin sort as the communist sort, but communist sort or better called Marxist sort refers to a totally different algorithm.

The core idea behind it is the redistribution of the commonwealth using a Marxist view. This means that the algorithm basically finds the average of the input dataset and replaces every element with the average, effectively sorting the list.

static void CommunistSort<T>(IList<T> values) where T: 
    IAdditionOperators<T, T, T>,
    IDivisionOperators<T, T, T>,
    IIncrementOperators<T>,
    new()
{
    T sum = new();
    T count = new();
    for (int i = 0; i < values.Count; i++)
    {
        sum += values[i];
        count++;
    }
    T average = sum / count;
    for (int i = 0; i < values.Count; i++)
    {
        values[i] = average;
    }
}

Late-stage Capitalist sort

Sticking to the theme of ideologies, the Late-stage capitalist sort finds the highest value and absorbs most of the wealth, leaving the other elements with a meager minimum wage.

static void LateStageCapitalistSort<T>(IList<T> values, T minimumWage) where T:
    IComparisonOperators<T, T, bool>,
    IAdditionOperators<T, T, T>,
    ISubtractionOperators<T, T, T>,
    new()
{
    T max = values[0];
    int maxIndex = 0;
    for (int i = 1; i < values.Count; i++)
    {
        //fintd the welthiest element
        if (values[i] > max)
        {
            max = values[i];
            maxIndex = i;
        }
    }

    T profit = new();
    for (int i = 0; i < values.Count; i++)
    {
        if (i != maxIndex)
        {
            profit += values[i] - minimumWage;
            values[i] = minimumWage; //minimum wage for everyone else
        }
    }
    values[values.Count -1] = values[maxIndex] + profit;
}