# C++ insertion sort implementation

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

• 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 – hoffmale Nov 14 '17 at 8:16

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