## Insertion Sort Algorithm Tutorial

To continue our discussion on sorting algorithms, in part 2 we are going to look at insertion sort. Insertion sort is one of the simplest ways of sorting and is quite different than merge or quicksort. Many people sort things like books, papers, and files almost exactly how insertion or one of it’s variations like selection sort works. Insertion sort breaks down into 4 steps

1. If length of array is less 2 then it’s sorted.
2. Start at array position i = 1 and loop through array where key = array[i]
3. Then for every key value loop through array backwards starting at position j = i – 1 moving all values < key up 1 position in the array.
4. When a value appears >= than place key value at 1 position above j since j >= key.

#### Insertion sort in C# source code

```    public class InsertionSortClass
{
private static byte[] numbers;
private static int size;

public static void sort(byte[] array)
{
if(array == null || array.Length < 2) return;
numbers = array;
size = numbers.Length;

insertionSort();
}

private static void insertionSort()
{
for(int i = 1; i<size; i++)
{
byte key = numbers[i];
int j = i - 1;
while (j >= 0)
{
if (key < numbers[j])
{
numbers[j + 1] = numbers[j];
j--;
}
else
{
break;
}
}
numbers[j + 1] = key;
}
}
}
```

#### Insertion sort in Java source code

```    public class InsertionSortClass
{
private byte[] numbers;
private int size;

public void sort(byte[] array)
{
if(array == null || array.length < 2) return;
this.numbers = array;
this.size = this.numbers.length;

insertionSort();
}

private void insertionSort()
{
for(int i = 1; i < this.size; i++)
{
byte key = this.numbers[i];
int j = i - 1;
while (j >= 0)
{
if (key < this.numbers[j])
{
this.numbers[j + 1] = this.numbers[j];
j--;
}
else
{
break;
}
}
this.numbers[j + 1] = key;
}
}
}
```

#### Insertion sort in Objective C source code

```//InsertionSortClass.h//

#import <Foundation/Foundation.h>

@interface InsertionSortClass : NSObject

-(void) sortWithArray:(UInt8*)array ofLength:(NSInteger) length;

@end

//InsertionSortClass.m//

#import "InsertionSortClass.h"

@interface InsertionSortClass()

@property (nonatomic) UInt8 *numbers;
@property (nonatomic) NSInteger size;

@end

@implementation InsertionSortClass

-(void) sortWithArray:(UInt8*)array ofLength:(NSInteger)length
{
//UInt8* is not an object but rather a pointer so use null not nil
if(array == null || length < 2) return;
self.numbers = array;
self.size = length;

[self insertionSort];
}

-(void) insertionSort
{
for(NSInteger i = 1; i < self.size; i++)
{
UInt8 key = self.numbers[i];
NSInteger j = i - 1;
while (j >= 0)
{
if (key < self.numbers[j])
{
self.numbers[j + 1] = self.numbers[j];
j--;
}
else
{
break;
}
}
self.numbers[j + 1] = key;
}
}
}
@end
```

Insertion sort in comparison to divide and conquer methods like merge or quicksort is a really fun and easy way to see how our everyday activities are really algorithms in our head working subconsciously.  Next time you look/”search” for something or organize/”sort” something, take a moment to think about how you are approaching this problem without noticing it. Why did you start where you did? What’s your next move? How do you know your getting closer to finding it?

While insertion sort is simple, it requires a lot of writes because the inner loop can require shifting large sections of the sorted portion of the array. In general, insertion sort will write to the array O(n2) times.