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 inplace 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 literal0
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 thekey < arr[0]
first. Consider an inner loop along the lines of keyint j; if (key < arr[0]) { // 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[0] 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.