I have written a sorting algorithm that is based on normalising values and counting. According to tests on my computer, it is faster than Array.Sort() for sizes up to 1 million. For a wide range of values, it is faster than sorting by counting. The only problems I see are memory usage and using temporary arrays with type ‘int?’, because I know not all languages support it. What data structure could I switch to that would not lose speed and reduce memory usage without losing the idea of index normalisation?

// randomize
        int[] array = new int[100_000_000];
        Random rand = new Random();
        for (int i = 0; i < array.Length; i++) array[i] = rand.Next(0, 100_000);

        // minimum and maximum
        int min = Int32.MaxValue;
        int max = Int32.MinValue;

        for (int i = 0; i < array.Length; i++)
        {
            int value = array[i];
            if (value < min)
            {
                min = value;
            }

            if (value > max)
            {
                max = value;
            }
        }

        // create two temporary arrays
        int?[] elements = new int?[array.Length];
        int?[] counts = new int?[array.Length];

        // sorting
        int index = 0;
        for (int i = 0; i < array.Length; i++)
        {
            index = (int)Math.Round(((((double)array[i] - min) / (max - min))) * (array.Length - 1)); // index retrieval through normalization

            if (!elements[index].HasValue)
            {
                elements[index] = array[i];
                counts[index] = 1;
            }
            else
            {
                counts[index]++; // repetition count
            }
        }

        // array rebuilding
        int indexArray = 0;
        for (int i = 0; i < elements.Length; i++)
        {
            if (elements[i].HasValue)
            {
                for (int j = 0; j < counts[i].Value; j++)
                {
                    array[indexArray++] = elements[i].Value;
                }
            }
        }

I tried to use Dictionary and List, but it didn’t give any positive result, even the memory usage is more.