Insertion sort

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;

    }