Given a task of implementing insertion sort, many people end up with following code

void insertionSort(int a[]){ for (int i = 0; i < a.length; i++) { for (int j = i; j > 0; j--) { int k = j-1; if( a[j] < a[k]){ int temp = a[j]; a[j] = a[k]; a[k] = temp; } } } }

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

#### Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).*Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.*

If you have

**understand**the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt

**My way to write insertion sort**

#### Correct Implementation

int[] insertionSort(int [] a ){ for (int j = 1; j < a.length; j++) { int i = j-1; while ( ( i >= 0 ) && a[i] > a[i+1] ) { int k = a[i]; a[i] = a[i+1]; a[i+1] = k; i -= 1; } } return a; }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of

*Insertion Sort.*