bin injections

#include <iostream>
#include <chrono>
#include <vector>

using namespace std;

int Binary_search(int *arr, int item, int low, int high) {
    int mid = (low + high) / 2;

    if (high <= low) {
        if (item > arr[low])
            item = low + 1;
        else item = low;
        return item;
    }

    if (item == arr[mid])
        return mid + 1;

    if (item > arr[mid])
        return Binary_search(arr, item, mid + 1, high);

    return Binary_search(arr, item, low, mid - 1);
}

void InsertionSort(int *arr, int size) {
    int j, location, num;
    for (int i = 1; i < size; i++) {
        j = i - 1;
        num = arr[i];
        location = Binary_search(arr, num, 0, j);
        while (j >= location) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = num;
    }
}

int main() {
    using namespace std;
    using std::chrono::duration_cast;
    using std::chrono::milliseconds;
    using std::chrono::system_clock;

    int size = 10;
    for (int j = 0; size < 1000000000; j++) {
        int *arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = rand();
        }
        auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
        InsertionSort(arr, size);
        auto end = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
        auto using_time = end - start;
        cout << size << " elements sorted for " << using_time << "ms\n";
        size *= 10;
    }
}