# Insertion Sort in C

Posted on

Problem

I have started studying algorithms using the classic CLRS book and decided to hone my C skills at the same time.

I wrote this function implementing insertion sort in C. I have tested it and verified that it works correctly. I would like to know whether it is readable and follows best practices.

Some points I’d like to receive feedback on:

1) Are the variable names well chosen? I have the impression that the convention in C is to use shorter names than in other languages and chose parameter names like arr and n accordingly. Would names like array and array_size have been better instead?

2) Instead of an array, the calling code could pass a null pointer to the function. I handle that using an int return value. Is that the best response?

3) Are the comments explaining the inner loop necessary?

``````#include <stddef.h>

#define INVALID_PARAMETER 1

/* Sorts an array of ints in-place using insertion sort.
* Returns INVALID_PARAMETER if a null pointer is passed
* as argument and 0 otherwise.
*/

int insertion_sort(int arr[], size_t n)
{
if (arr == NULL) {
return INVALID_PARAMETER;
}

for(size_t i = 1; i < n; i++) {
int key = arr[i];

/* Look through the array backwards until finding where key must be
* inserted. If the element we are looking at now is bigger than key,
* it is displaced forward. Stop when an element smaller than key is
* found or the start of the array is reached. */
size_t j;
for(j = i; j > 0 && arr[j - 1] > key; j--) {
arr[j] = arr[j - 1];
}

/* After the loop, j is either 0, what means that no element smaller
* than key was found and it must be the first element in the sorted
* array, or j is the position after the first element found that was
* smaller than key and so it is where key must be inserted. */
arr[j] = key;
}

return 0;
}
```
``````

Solution

• Using a symbolic constant (`INVALID_PARAMETER`) along with a literal `0` as a return value is not the cleanest solution. As a side note, a return value signifying an error is traditionally negative.

• The best kept secret of insertion sort is the fact that the `j > 0 && arr[j - 1] > key` termination condition of an inner loop is suboptimal. It tests two conditions in every iteration. It is possible to get away with only one test: check wether the `key < arr` first. Consider an inner loop along the lines of key

``````    int j;
if (key < arr) {
// Now key shall for sure become leftmost. Don't bother testing values.
for (j = i; j > 0; j--) {
arr[j] = arr[j - 1];
}
} else {
// Now arr is a natural sentinel. Don't bother testing indices.
for (j = i; key < arr[j - 1]; j--)
arr[j] = arr[j - 1];
}
}
arr[j] = key;
``````
• Otherwise, LGTM.