Does this sorting algorithm have a name?

Question

Long story short, I came up with this algorithm, but I doubt that I invented something. So what's the name of this?

I know it has a lot of restrictions in multiple areas. For instance this implementation can not sort numbers higher than UInt16, and is limited to a maximum of int.MaxValue occurences. I also might have some array boundary issue somewhere. And it already eats RAM like cake :)

The actual algorithm is implemented in the CustomSort method. The rest is the code I used for testing.

  class Program
    {
        static Random r = new Random((int)DateTime.Now.Ticks);

        static int[] GetRandomIntegers(int count)
        {
            int[] result = new int[count];
            for (int i = 0; i < count; i++)
            {
                int randomNumber = r.Next(0, UInt16.MaxValue);
                result[i] = randomNumber;
            }
            return result;
        }

        public static int[] CustomSort(int[] itemsToSort)
        {
            // Consider each number in the array to sort as a "memory address" or index of a huge array
            // which has a default value of zero and gets incremented every time that number is encountered
            // Example:
            // Array to sort: 5, 2, 2, 7, 5, 1, 3
            // Create an array of at most 7 dimensions. 
            //      Since that number takes time to find, bind the algorithms limit of maximum numbers to UInt16 and skip that step. Prefer more ram over processor time :)
            // First item, 5 encountered - Take index 5 in result array and add one, result is 1
            // Second item, 2 encountered - Take index 2 in result array and add one, result is 1
            // Third item, 2 encountered - Take index 2 in result array and add one, result is 2
            // Loop until done
            // Now the temp array will contain how many times each number was encountered. The array index is the number itself, and traversing the array from 0 to N
            // will provide the count of how many times that number was encountered
            // For each number not encountered the value at index will stay 0 and just consume RAM :)

            int[] temp = new int[UInt16.MaxValue];
            for (int i = 0; i < itemsToSort.Length; i++)
            {
                temp[itemsToSort[i]]++;
            }

            // Final step, create resulting sorted array by looping over the temp array and creation of that many items as the value of the current index
            int[] result = new int[itemsToSort.Length];
            int current = 0;
            for (int i = 0; i < UInt16.MaxValue; i++)
            {
                int count = temp[i];
                for (int j = 0; j < count; j++)
                {
                    result[current] = i;
                    current++;
                }
            }
            return result;
        }

        static void Main(string[] args)
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();

            int[] sortMe = GetRandomIntegers(1000000000);
            int[] arraySorted = new int[sortMe.Length];
            watch.Stop();
            Console.WriteLine($"Random generation of '{sortMe.Length}' elements took: {watch.Elapsed}");

            Array.Copy(sortMe, 0, arraySorted, 0, sortMe.Length);
            watch.Restart();
            Array.Sort(arraySorted);
            watch.Stop();
            Console.WriteLine("Array sort(Heap/Quicksort) took: " + watch.Elapsed);

            watch.Restart();
            int[] mySorted = CustomSort(sortMe);
            watch.Stop();
            Console.WriteLine("Custom sort took: " + watch.Elapsed);

            watch.Restart();
            bool isEqual = Enumerable.SequenceEqual(mySorted, arraySorted);
            watch.Stop();
            Console.WriteLine($"Equality check: {isEqual} took: {watch.Elapsed}");
            Console.WriteLine("Done");

            Console.ReadLine();
        }
    }

Answer 1

The algorithm you’ve come up with is counting sort!

Answer 2

It's called the Counting Sort. There is also a modification of this algorithm, called Radix Sort. More details: https://www.geeksforgeeks.org/radix-sort/