Attempt at a sorting algorithm

Question

I've been playing around and reading up on some sorting algorithms, and I've decided to try writing my own. It turned out to be quite fast (compared to the others shown in the image below).

I'm very curious to know a little bit about it:

• Does my algorithm already have a name?
• What are the downsides to it (other than it being really stupid to sort { 900000, 1 } with it)?
• Why is it not a good solution in general?
• Any suggestions for optimisation?

static int[] MySort(int[] input) { int minValue = input.Min() - 1; int[] tempArr = new int[input.Max() - minValue]; //{1,3,3,5} becomes: //{1,0,2,0,1} one 1's, two 3's, one 5's. for (int i = 0; i < input.Length; i++) tempArr[input[i] - minValue - 1] += 1; //AddNumbers to old array. and add minValue. int g = 0; for (int j = 0; j < tempArr.Length; j++) { if (tempArr[j] != 0) { for (int i = 0; i < tempArr[j]; i++) { input[g] = j + minValue + 1; g++; } } } return input; } 

Performance screenshot:

Answer 1

Does my algorithm already have a name?

It's called counting sort.

What are the downsides to it? (Other than it is really stupid to sort { 900000, 1 } with it.)

That's exactly the major disadvantage of the algorithm: it doesn't work well if the range of values is large.

Why is it not a good solution in general?

Because it can sort only integers. You can't use it to sort floating point numbers, strings or any other type that doesn't behave as an integer.

Any suggestions for optimization?

The condition if (tempArr[j] != 0) is completely useless. If you leave it out, the code will work exactly the same.

Answer 2

I know this is a fairly old question, but I'd like to point something out.

While i and j are commonly used as "counter" variables, they only serve to obfuscate the code in this case. By time we make it to g, it's very difficult indeed to tell which variable stands for what. These should all have meaningful names for Mr. Maintainer's sake.

This is a little more verbose, but (I think) a little easier to understand. Particularly considering that it's easy to see now that the i in the initial loop, is not the same i as the one nested in the second loop.

static int[] MySort(int[] input) { int minValue = input.Min() - 1; int[] tempArr = new int[input.Max() - minValue]; //{1,3,3,5} becomes: //{1,0,2,0,1} one 1's, two 3's, one 5's. for (int inputCounter = 0; inputCounter < input.Length; inputCounter++) tempArr[input[inputCounter] - minValue - 1] += 1; //AddNumbers to old array. and add minValue. int itemCounter = 0; for (int tempCounter = 0; tempCounter < tempArr.Length; tempCounter++) { if (tempArr[tempCounter] != 0) { for (int i = 0; i < tempArr[tempCounter]; i++) { input[itemCounter] = tempCounter + minValue + 1; itemCounter++; } } } return input; }