#include <iostream>
#include <time.h>
#include <algorithm>
#include<cstdlib>
using namespace std;

void SelectionSort()
{
    int n=100000,arr[n];
    srand(time(0));
    for(int i=0; i<n; i++)
    {
        arr[i]=1+rand()%100000;
    }
    int minimum;
    clock_t t;
    t=clock();
    for (int i=0; i<n-1; i++)
    {
        minimum=i;
        for(int j=1; j<n-1; j++)
        {
            if(arr[j]<arr[minimum])
                minimum=j;
        }
        swap(arr[minimum],arr[i]);
    }
    cout<<"Selection Sorting Time : "<<float(clock()-t)/CLOCKS_PER_SEC<<"Seconds"<<endl;
}
void InsertionSort ()
{
    int n=100000,arr[n];
    srand(time(0));
    for(int i=0; i<n; i++)
    {
        arr[i]=1+rand()%100000;
    }
    clock_t t;
    t=clock();
    for(int i=0; i<n-1; i++)
    {
        if(arr[i]>arr[i+1])
        {
            swap(arr[i],arr[i+1]);
            for(int j=i; j>=0; j--)
            {
                if(arr[j]<arr[j-1])
                    swap(arr[j],arr[j-1]);
            }
        }
    }

    cout<<"------------------------"<<endl<<"Insertion Sorting Time : "<<float(clock()-t)/CLOCKS_PER_SEC<<"Seconds"<<endl;
}
void BubbleSort()
{
    int n=100000,arr[n];
    srand(time(0));
    for(int i=0; i<n; i++)
    {
        arr[i]=1+rand()%100000;
    }
    clock_t t;
    t=clock();
    for(int i=0; i<n-1; i++)
    {
        for(int j=0; j<n-1-i; j++)
        {
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
            }
    }
    cout<<"------------------------"<<endl<<"Bubble Sorting Time : "<<float(clock()-t)/CLOCKS_PER_SEC<<"Seconds"<<endl;
}
void Mc(int arr[],int a,int b,int c)
{
    int f=c-a+1,s=b-c+1,a1[f],a2[s];
    srand(time(0));
    clock_t t;
    t=clock();
    for(int i=0; i<f; i++)
        a1[f]=arr[i];
    for(int j=0; j<s; j++)
        a2[s]=arr[j];
    int counter1=0,counter2=0,z=0;
    for(int t=0; t<counter1&&t<counter2; t++)
    {
        if(a1[counter1]<=a2[counter2])
        {
            arr[t]=a1[counter1];
            counter1++;
        }
        else
        {
            arr[t]=a2[counter2];
            counter2++;
        }
        z=t;
    }
    while(counter1<f){
        arr[z]=a1[counter1];
        counter1++; z++;
    }
    while(counter2<s){
        arr[z]=a2[counter2];
        counter2++; z++;
    }
cout<<"------------------------ \n"<<"Merge Sorting Time : "<<float(clock()-t)/CLOCKS_PER_SEC<<"Seconds"<<endl;
}


void MergeSort (int arr[], int l, int r)
{
    int mid = (l + r) / 2;
    if (l < r) {
        MergeSort(arr,l,mid);
        MergeSort(arr,mid + 1, r);
        Mc(arr, l, mid, r);
    }
}

int main()
{
    srand(time(0));
    const int N = 1e5;
    int arr[N];
    for (int i = 0; i < N; i++) {
        arr[i] = rand();
    }

    SelectionSort();
    InsertionSort();
    BubbleSort();
    MergeSort(arr, 0, N - 1);
    return 0;
}