#include <iostream>
using namespace std;

void printArray(int arr[], int n){
    int i;
    for(i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

void linearSearch(int a[], int key, int n){
    int i;
    for(i = 0; i < n; i++){
        if(a[i] == key){
            cout << " Found at: " << i << " th index" << endl;
            return;
        }
        else
            cout << "Not Found" << endl;
    }
}

void binarySearch(int a[], int key, int n){
    int i, mid;
    int high = n;
    int low = 0;
    while(low < high){
        mid = (low + high) / 2;
        if(a[mid] == key){
            cout << "Found at: " << mid << " th index" << endl;
            return;
        }
        else if(a[mid] < key){
            low = mid + 1;
        }
        else if(a[mid] > key)
            high = mid - 1;
        else
            cout << "Not found" << endl;
    }
}

void bubbleSort(int a[], int n){
    int i, j;
    int temp = 0;
    for(i = 0; i < n; i++){
        for(j = 0; j < n - i - 1; j++){
            if(a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

void selectionSort(int a[], int n){
    int i, j;
    for(i = 0; i < n; i++){
        int minIndex = i;
        for(j = i + 1; j < n; j++){
            if(a[minIndex] > a[j]){
                minIndex = j;
            }
        }
        int temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
        printArray(a, n);
    }
}

void insertionSort(int a[], int n){
    int i, j, key;
    for(i = 1; i < n; i++){
        key = a[i];
        j = i - 1;
        while(a[j] > key && j >= 0){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
        printArray(a, n);
        cout << endl;
    }
}

int quickPartition(int a[], int low, int high){
    int i, j, pi;
    pi = high;
    i = low - 1;
    int temp;
    for(j = low; j < high; j++){
        if(a[j] < a[pi]){
            i++;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        cout << "In side loop j: " << j << " th iteratio" << endl;
        cout << endl;
        cout << endl;
        printArray(a, high+1);
    }
    temp = a[high];
    a[high] = a[i+1];
    a[i+1] = temp;
    cout << "before return " << i << " th iteratio" << endl;
    cout << endl;
    cout << endl;
    printArray(a, high+1);
    return i + 1;
}

void quickSort(int a[], int low, int high){
    if(low < high){
        int pi = quickPartition(a, low, high);
        quickSort(a, low, pi-1);
        quickSort(a, pi+1, high);
    }
}

void merge(int a[], int l, int mid, int h){
    int n1 = (mid + 1 - l);
    int n2 = (h - mid);
    int al[n1];
    int ar[n2];
    int x, y;
    for(x = 0; x < n1; x++){
        al[x] = a[l+x];
    }
    for(x = 0; x < n2; x++){
        ar[x] = a[mid+1+x];
    }
    int i = 0;
    int j = 0;
    int k = l;
    while(i < n1 && j < n2){
        if(al[i] < ar[j]){
            a[k] = al[i];
            i++;
        }
        else{
            a[k] = ar[j];
            j++;
        }
        k++;
    }
    while(i < n1){
        a[k] = al[i];
        i++;
        k++;
    }
    while(j < n2){
        a[k] = ar[j];
        j++;
        k++;
    }
}

void mergeSort(int a[], int l, int h){
    if(l < h){
        int mid = (l + h) / 2;
        mergeSort(a, l, mid);
        mergeSort(a, mid+1, h);
        merge(a, l, mid, h);
    }
}

int main()
{
    cout << "Before Sorting" << endl;
    int arr[10]{3, 6, 9, 13, 16, 18, 24, 23, 29, 33};
    int arr1[10]{34, 46, 2, 18, 36, 12, 39, 27, 45, 69};
    cout << endl;
    cout << endl;
    printArray(arr1, 10);
    mergeSort(arr1, 0, 9);
    cout << "After Sorting" << endl;
    printArray(arr1, 10);
    return 0;
}