# Insert sort algorithm

• May 26th, 2009, 08:33 AM
Alysosh
Insert sort algorithm
I'm trying to understand the algorithm for insert sort for efficiency.

Why does 2 + 2 x 2 + .... 2 X(n-1) = n squared - n?

what's the relationship between the two?

thanks.
• May 26th, 2009, 09:28 AM
JavaPF
Re: Insert sort algorithm
Hello Alysosh,

Insertion sort - Wikipedia, the free encyclopedia

I found this good example here for you to take a look at:

Code :

```class ArrayIns { private long[] a; private int nElems;   public ArrayIns(int max) { a = new long[max]; nElems = 0; }   public void insert(long value) { a[nElems] = value; nElems++; }   public void display() { for (int j = 0; j < nElems; j++) System.out.print(a[j] + " "); System.out.println(""); }   public void insertionSort() { int in, out;   for (out = 1; out < nElems; out++) { long temp = a[out]; in = out; while (in > 0 && a[in - 1] >= temp) { a[in] = a[in - 1]; --in; } a[in] = temp; } } }```

Code :

```class insertSort { public static void main(String[] args) { int maxSize = 100; ArrayIns arr; arr = new ArrayIns(maxSize);   arr.insert(77); arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33);   arr.display();   arr.insertionSort();   arr.display(); } }```

Example output:

Quote:

77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99