#include <concepts>
#include <vector>
namespace mehara::sort {
template <typename T>
requires std::totally_ordered<T>
void insertion_sort(std::vector<T>& array){
for (auto outer_index = 1; outer_index < array.size(); outer_index++) {
auto key = array[outer_index];
auto inner_index = outer_index - 1;
while (inner_index >= 0 && array[inner_index] > key) {
array[inner_index + 1] = array[inner_index];
inner_index = inner_index - 1;
}
array[inner_index + 1] = key;
}
}
}