#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::list;
using std::iterator;

// BinarySort combines the idea of Binary search and Quick sort.
// We used a pivot, a low, and a high to sort.
// In the outer loop, we select one pivot for each time, and compare it with rest elements.
// low and high are assigned to determine the right position of pivot.
// when low meets high, we got the right position of pivot.
// Finally, swap previous elements until the pivot arrives its position.
// When dealing with iteration operations, use std::advance or std::distance! Because list doesn't allow those operations
void BinarySort(vector<int>::iterator begin, vector<int>::iterator end){

    // pivot go through each element in the vector
    for(vector<int>::iterator pivot=begin;pivot!=end;++pivot){

        // initialize low and high bound
        vector<int>::iterator low = begin;
        vector<int>::iterator high = pivot;

        // binary search the pivot to determine its right position
        while(low != high){
            // use a miidle to keep low and high moving
            // list doesn't allow this!
            vector<int>::iterator middle = low+(high-low)/2;

            if(*pivot>=*middle){
                // iterator addition!
                low = middle+1;
            }
            else {
                high = middle;
            }
        }
        // swap iteratively to move pivot to its right position
        for(vector<int>::iterator J = pivot; J!=low;--J){
            // J-1 is not allowed in list, too!
            std::swap(*J,*(J-1));
        }
    }

}

int main(int argc, char **argv){

    // vector
    vector<int> v= {13, 2, 3, 7, 1, 4, 22, 5};

    // sort
    BinarySort(v.begin(), v.end());
    cout<< "After Binary Sort"<<endl<<"vector"<<endl;
    // output result
    for(auto x:v){
        cout<<x<<" ";
    }
    cout<<endl;
    return 0;
}