/**
  * insertion sort, vector
  */
void i_sort(vector<int> & data){
    for(int i = 0; i < data.size()-1; i++){
        // out of order element?
        if ( data[i] > data[i+1] ){
            // pull data[i+1] to its proper position.
            // the value needs to be stored.
            int insert_value = data[i+1];
            int insert_index = i;
            // stop at index 0 or at the correct spot.
            while( insert_index && data[insert_index] > insert_value ){
                // move up value in list to make room for insertion.
                data[insert_index+1] = data[insert_index];
                insert_index--;
            }
            data[insert_index+1] = data[insert_index];
            data[insert_index] = insert_value;
        }
    }
}
 
 

LyoqCiAgKiBpbnNlcnRpb24gc29ydCwgdmVjdG9yCiAgKi8Kdm9pZCBpX3NvcnQodmVjdG9yPGludD4gJiBkYXRhKXsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBkYXRhLnNpemUoKS0xOyBpKyspewogICAgICAgIC8vIG91dCBvZiBvcmRlciBlbGVtZW50PwogICAgICAgIGlmICggZGF0YVtpXSA+IGRhdGFbaSsxXSApewogICAgICAgICAgICAvLyBwdWxsIGRhdGFbaSsxXSB0byBpdHMgcHJvcGVyIHBvc2l0aW9uLgogICAgICAgICAgICAvLyB0aGUgdmFsdWUgbmVlZHMgdG8gYmUgc3RvcmVkLgogICAgICAgICAgICBpbnQgaW5zZXJ0X3ZhbHVlID0gZGF0YVtpKzFdOwogICAgICAgICAgICBpbnQgaW5zZXJ0X2luZGV4ID0gaTsKICAgICAgICAgICAgLy8gc3RvcCBhdCBpbmRleCAwIG9yIGF0IHRoZSBjb3JyZWN0IHNwb3QuCiAgICAgICAgICAgIHdoaWxlKCBpbnNlcnRfaW5kZXggJiYgZGF0YVtpbnNlcnRfaW5kZXhdID4gaW5zZXJ0X3ZhbHVlICl7CiAgICAgICAgICAgICAgICAvLyBtb3ZlIHVwIHZhbHVlIGluIGxpc3QgdG8gbWFrZSByb29tIGZvciBpbnNlcnRpb24uCiAgICAgICAgICAgICAgICBkYXRhW2luc2VydF9pbmRleCsxXSA9IGRhdGFbaW5zZXJ0X2luZGV4XTsKICAgICAgICAgICAgICAgIGluc2VydF9pbmRleC0tOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGRhdGFbaW5zZXJ0X2luZGV4KzFdID0gZGF0YVtpbnNlcnRfaW5kZXhdOwogICAgICAgICAgICBkYXRhW2luc2VydF9pbmRleF0gPSBpbnNlcnRfdmFsdWU7CiAgICAgICAgfQogICAgfQp9Cgo=