vector<int> sortArray(vector<int>& nums) {
//insertion sort.
// [sorted | ... > x ... | x | ....]
// after sort
// [smaller than x | x | larger than x| not sorted]
/*
we need to move x to the right place
The right place means everything larger than x
is to x's right (till the sorted boundary)
everything smaller than x is to its left(till the beginning)
In insertion sort, during the kth iteration, the first k + 1th
element are in order (relatively)
So this loop invariant, when k == nums.size() means the whole
array is in order relatively. IF not show contradiction.
*/
int cur_elem_pos = 1;
for(;cur_elem_pos < nums.size() ; cur_elem_pos ++){
int insert_index = cur_elem_pos;
int elem_to_be_insert = nums[cur_elem_pos];
while(insert_index > 0 &&
nums[insert_index - 1] > elem_to_be_insert){
nums[insert_index] = nums[insert_index - 1];
insert_index --;
}
nums[insert_index] = elem_to_be_insert;
}
return nums;
}