Сортировка бинарными вставками

/*Бинарными вставками*/
int sort_bin (int* data, int size) 
{
        int i;
        for (i = 0; i < size; i++) {
                int pos = -1;
                int start = 0;
                int end = i - 1;
                int numToInsert = data[i];
                // Находим место вставки с помощью бинарного поиска
                while (start <= end && !(pos != -1)) {
                        int middle = (start + end) / 2;
                        if (numToInsert > data[middle]) {
                                start = middle + 1;
                        } else if (numToInsert < data[middle]) {
                                end = middle - 1;
                        } else {
                                pos = middle;
                        }
                }
                if(end < 0){
                        // определяем позицию в случае если элемент меньше всех отсортированных
                        pos = 0;
                } else if(start >= i){
                        // определяем позицию в случае если элемент больше всех отсортированных
                        pos = i;
                }
                if (pos < i) {
                        // сдвигаем элементы вправо на одну позицию
                        int j;
                        for (j = i; j > pos; j--) {
                                data[j] = data[j - 1];
                        }
                        data[pos] = numToInsert;
                }
        }
        return *data;
}
/*-=End-=*/

#include <iostream>
#include <ctime>
using namespace std;
 
void input_array(short* A, unsigned short n);
void output_array(short* A, unsigned short n);
void sort_array(short* A, unsigned short n);
 
void main()
{
    unsigned short n;
    cout << "Enter the number of elements: ";
    cin >> n;
    short* A = new short[n];
    input_array(A,n);
    output_array(A,n);
    sort_array(A,n);
    output_array(A,n);
}
 
void input_array(short* A, unsigned short n)
{
    srand((unsigned)time(NULL));
    for (unsigned short i = 0; i < n; i++)
        A[i] = rand()%200 - 100;
}
 
void output_array(short* A, unsigned short n)
{
    for (unsigned short i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << "\n";
}
 
void sort_array(short* A, unsigned short n)
{
    short x;
    short left;
    short right;
    short sred;
    for (short i = 1;  i < n; i++) 
        if (A[i-1] > A[i]){
            x = A[i];
            left = 0;  
            right = i-1;  
            do {
                sred = (left + right)/2;    
                if  (A[sred] < x ) left = sred + 1;  
                else  right = sred - 1;      
            } while (left <= right);
            for (short j = i-1; j>=left; j--)
                A[j+1] = A[j];  
            A[left] = x;
      }
}

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <time.h>
 
using namespace std;
 
void out(int arr[], int size);
void in_rand(int arr[], int size);
 
int bin_insert(int arr[], int left, int right, int i, int& num_of_cmp)
{
    if (left > right)
        return left;    
 
    int mid = (left + right) / 2;
 
    if (arr[i] > arr[mid]){
        num_of_cmp++;
        bin_insert(arr, mid + 1, right, i, num_of_cmp);
    }
 
    else{
        num_of_cmp++;
        bin_insert(arr, left, mid - 1, i, num_of_cmp);
    }
}
 
void shift_right(int arr[], int i, int index, int& num_of_swap)
{
    int var_to_swap = arr[i];
    for (int k = i; k > index; k--){
        arr[k] = arr[k - 1];
        num_of_swap++;
    }
    arr[index] = var_to_swap;
    num_of_swap++;
}
 
int main()
{
    const int size = 10000;   // SIZE
    int arr[size];
    int num_of_cmp = 0, num_of_swap = 0;
    int index = 0;
 
    in_rand(arr, size);
    
    int time = clock();
    for (int i = 1; i < size; i++){
        if (arr[i] < arr[i - 1]){
            shift_right(arr, i, bin_insert(arr, 0, i - 1, i, num_of_cmp), num_of_swap);
        }
    }
    time = clock() - time;
    cout << endl << "Array with " << size << " elements was sorted for " << time << "ms" << endl << num_of_cmp << " compare and " << num_of_swap << " swap.\n\nPress the Enter to show sorted array." << endl;
 
 
    cout << endl << endl;
    _getch();
    out(arr, size);
 
    _getch();
    return 0;
}
 
void in_rand(int arr[], int size)
{
    srand(time(0));
 
    for (int i = 0; i < size; i++)
        arr[i] = rand() % 100;
}
 
void out(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << "  ";
}