Insertion Sort in C

Question

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;
}
```

Answer 1

• 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[0] first. Consider an inner loop along the lines of key

      int 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.