#include
#include
#include
#include
#include
using namespace std;

void input(int [], int);
int binarySearch(int [], int, int, int);
void insertionSort(int [], int);
void bubbleSort(int [], int);
void swap(int*, int*);
void selectionSort(int [], int);
void time_it(double, double, string);
void modified_bubbleSort(int [], int);
void mergeSort(int [], int, int);
void merge(int [], int, int, int);
void cpu_clock_cycles(double, double);

int binarySearch(int a[], int low, int high, int x) {
    if (high  a[low])?  (low + 1): low;
    int mid = (low + high)/2;
    if(x == a[mid])
        return mid+1;
    if(x > a[mid])
        return binarySearch(a, mid+1, high, x);
    return binarySearch(a, low, mid-1, x);
}

void insertionSort(int a[], int n) {
    int loc, i, j, selected;
    for(i=1; i= loc){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
}

void bubbleSort(int b[], int n) {
    int i, j;
    for(i=n-1;i>=0;i--) {
        for(j=0; j