C++ insertion sort implementation

Question

I was wondering if this implementation of insertion sort could be improved. Are there any things that I have done wrong?

template<typename Element>
void insertion_sort(Element arr[], size_t size) {
 size_t index, index_sorted;
 for (index = 0u; index < size; ++index) {
 auto temp = arr[index];
 index_sorted = index - 1;
 while (arr[index_sorted] >= 0 && arr[index_sorted] > temp) {
 arr[index_sorted + 1] = arr[index_sorted--];
 }
 arr[index_sorted + 1] = temp;
 }
}

• hoffmale: Are you using C++17? If yes, please add the c++17 tag. If not, the line arr[index_sorted + 1] = arr[index_sorted--]; is undefined behavior. More info

Answer 1

Small nitpicks

• The for loop can be started from 1, as the iteration with 0 doesn't actually do anything.
• Prefer to reduce the scope of variables if possible. This allows better reasoning for the compiler/optimizer, and makes the code more readable because the variable declaration is nearer to the actual usage.
• The check arr[index_sorted] >= 0 in the while loop should probably be index_sorted >= 0u (after all, Element might not be comparable to integers), but this is true in all cases (-1 for an unsigned integer type is equal to that type's maximum value). However, even checking this becomes unnecessary if the first iteration starts at 1.
• The array elements could possibly be moved to their new locations (this might improve performance in some cases).

template<typename Element>
void insertion_sort(Element arr[], size_t size) {
 for (auto index = 1u; index < size; ++index) {
 auto temp = std::move(arr[index]);
 auto index_sorted = index - 1;
 while (arr[index_sorted] > temp) {
 arr[index_sorted + 1] = std::move(arr[index_sorted--]);
 }
 arr[index_sorted + 1] = std::move(temp);
 }
}

Technically, the size of the array could be deduced automatically by taking a reference (though it has an ugly syntax). However, by taking an explicit size parameter one can sort a partial array, so I'd prefer the flexibility of this approach.