bin insert sort

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

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 std::chrono::duration_cast;
    using std::chrono::milliseconds;
    using std::chrono::system_clock;
    int size = 10;
    while (size < 1000000) {
        for (int k = 0; k < 10; k++) {

            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 << k + 1 << ") " << size << " elements sorted for " << using_time << "ms\n";
        }
        size *= 10;
    }
}