If you're just looking for a reasonably good solution, don't implement it yourself, use the STL library instead:
http://www.cplusplus.com/reference/algorithm/sort/[
^]
As for optimizing your code for the purpose of learning how to do 'stuff', the thing about insertion is that it's rather inefficient on an array-like data structure! A much more efficient implementation would use a list instead. You could simply use
std::list
for that purpose and focus on the details of your sort algorithm - no point in reinventing the
wheel list ;-)