# Performing insertion sort in C#

This is my code in C# for performing insertion sort:

static int[] performInsertionSort(int[] inputarray)
{
for (int i = 0; i < inputarray.Length-1; i++)
{
int j = i+1;

while (j>0)
{
if (inputarray[j-1] > inputarray[j])
{
int temp = inputarray[j-1];
inputarray[j - 1] = inputarray[j];
inputarray[j] = temp;

}
j--;
}
}
return inputarray;
}


Is there a way to optimize this code? Can I make further changes to it?

-

Your sorting logic is dependent upon the specific type.

"Separate your data representation from logic." you must take advantage of the generic to reuse the same component to sort any kind of object. In case of class you can specify comparer to sort the values.

Naming convention should be followed. i and j does not make sense and in c# standard method naming convetion should Pascal case , should not start with lowercase.

Rest logic looks good.

public static T[] PerformInsertionSort<T>(T[] inputarray, Comparer<T> comparer=null)
{
var equalityComparer = comparer ?? Comparer<T>.Default;
for (var counter = 0; counter < inputarray.Length - 1; counter++)
{
var index = counter + 1;
while (index > 0)
{
if(equalityComparer.Compare(inputarray[index - 1],inputarray[index])>0)
{
var temp = inputarray[index - 1];
inputarray[index - 1] = inputarray[index];
inputarray[index] = temp;
}
index--;
}
}
return inputarray;
}

-
Making it type-independent results in quite heavy hit in performance. For array of 65535 random integers Kyle sort took ~10k milliseconds, your <T>Sort jumped to ~19k... and Array.Sort is evil and needed just 5ms (but its basically native quicksort implementation so its not fair to compare with it) –  PTwr Aug 14 '14 at 9:22
How is counter and index any better than i and j? –  svick Aug 14 '14 at 11:02
@svick , better meaning is good rather i and j. it could be anything better which you want –  paritosh Aug 14 '14 at 11:04
@PTwr In general, I agree. But my question was very specific: how are the proposed names counter and index, which also don't say anything about what or why are they counting better than i and j? People know that it's common to use i as loop counter and j if you need a second one. But counter and index would confuse me, because I don't see any meaning behind those names (except that they're also probably loop counters). –  svick Aug 14 '14 at 12:48
@Snowbody "Is there a way to optimize this code?" - Performance is of concern as it is main part of optimization. –  PTwr Aug 16 '14 at 18:41

static int[] performInsertionSort(int[] inputarray)
{
for (int i = 0; i < inputarray.Length-1; i++)
{
int j = i+1;

while (j>0)
{
if (inputarray[j-1] > inputarray[j])
{
int temp = inputarray[j-1];
inputarray[j - 1] = inputarray[j];
inputarray[j] = temp;

}
j--;
}
}
return inputarray;
}


I can see a couple of things that I would do differently.

Instead of using a while on the inside I would probably use another for loop because it would look a little bit cleaner. I would also change the name of inputarray to inputArray because of common naming schemes.

Personally I think for something this simple i and j are fine, if the operations become more complex and you aren't just sorting random numbers, then you would have something meaningful that you could name them, so I would just keep i and j.

Here is what my version would look like:

static int[] performInsertionSort(int[] inputArray)
{
for (int i = 0; i < inputArray.Length-1; i++)
{
for (int j = i + 1; j > 0; j--)
{
if (inputArray[j-1] > inputArray[j])
{
int temp = inputArray[j-1];
inputArray[j-1] = inputArray[j];
inputArray[j] = temp;
}
}
}
return inputArray;
}


I wanted to test this to make sure that it worked correctly, here is my code with the output programmed into the application.

Insertion sort revised with output to console

-