C# sorting a list with O(N) performance

[simonthecat]

For a college class I am trying to write a program that is has linear performance. The solution I wrote depends upon having a list that is sorted. Well, my teacher told me that I would not get full credit if I have to use the C# sort function. So, I am trying to write my own sort function that is linear. Its doing some strange stuff with the variables, but it seems close. Any ideas on if what I am trying to do looks plausible? Here is what I have so far:

        static void linearIntListSort(ref List<int> inputList)
        {
            bool runLoop = true;            
            int index = 0;
            int numberSorted = 0;
            int dummyVariable = -2147483648;
            int lastNumber = dummyVariable;
            int listSize = inputList.Count;
            while (runLoop)
            {
                if (lastNumber > inputList[index])
                {
                    inputList[(index-1)] = inputList[index];
                    inputList[index] = lastNumber;
                }
                else
                {
                    numberSorted++;
                }

                if (numberSorted == listSize)
                {
                    runLoop = false;
                }

                lastNumber = inputList[index];
                if (index + 1 == listSize) // if end of list is reached
                {
                    index = 0;
                    numberSorted = 0;
                    lastNumber = dummyVariable;
                }

                index++;
            }
        }

 

[misson]

No, that won't work. Your loop is basically one iteration of a bubble sort. It will place the maximal element at the end of the list, and bubble a few other elements upwards, but won't sort the list. Try the list 2,1,0.

All comparison-based sorts have a lower time-complexity bound of Ω(n*log(n)). Fortunately for you, there are other properties of integers to base sorting on, which result in the Ω(n) performance you're looking for. Ask your teacher for details, or read over the linked pages closely.