The following is the insertion sort algorithm for sorting a array in non-decreasing order and non-increasing order respectively.

As you will see that, insertion sort is a stable sorting algorithm. What is stable sorting?

Only the function for insertion sort is given. Viewers are advised to write the driver program (**main()**) themselves.

void insertionSort(int *a, int n){ // a is the input array. n is the size of the array int i, j, key; for(j=1;j<n;j++){ i = j-1; key = a[j]; while(i>=0 && a[i] < key){ a[i+1] = a[i]; i--; } a[i+1] = key; } }

To sort an array in non-increasing order a minor modification has to be done. Can you observe the change made in the following code?

void insertionSort(int *a, int n){ // a is the input array. n is the size of the array int i, j, key; for(j=1;j<n;j++){ i = j-1; key = a[j]; while(i>=0 && a[i] < key){ a[i+1] = a[i]; i--; } a[i+1] = key; } }