UPDATE : Check this more general comparison ( Bubble Sort Vs Selection sort Vs Insertion Sort Vs Merge Sort Vs Merge Sort Vs Quick Sort )

Before the stats, You must already know what is Merge sort, Selection Sort, Insertion Sort, Arrays, how to get current time.

Selection Sort

Selection Sort Complexity is O(n^2).

void selectionSort(int* a, int size)
{
    for (int i = 2; i < size; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            if (a[j] < a[j - 1])
            {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

Insertion Sort

Insertion Sort Complexity is O(n^2).

void insertionSort(int* a, int size)
{
    for (int i = 1;i < size;i++)
    {
		int x = a[i];
		int j = i;
        while (j > 0 && a[j-1] > a[j])
        {
			int temporaryVariable=a[j];
			a[j] = a[j-1];
			a[j-1]=temporaryVariable;
			j --;
        }
        a[j] = x;
    }
}

Merge Sort

Merge sorting complexity is O(nlogn).

 

void merge(int* a, int first, int middle, int last)
{
	int j,i0,i1;
    i0 = first;
    i1 = middle;

    // While there are elements in the left or right runs
    
    for (j = first; j < last; j++) {
        // If left run head exists and is <= existing right run head.
        if (i0 < middle && (i1 >= last || a[i0] <= a[i1])){
            b[j] = a[i0];
            i0++;
		}
        else{
            b[j] = a[i1];
            i1++;
		}
    } 
	
}
void split(int* a, int first, int last)
{
	
    if (last - first<2)
		return;
    int middle = floor((first + last) / 2);
    //cout<<first<<" "<<middle<<" "<<last<<endl;
    split(a, first, middle);
    split(a, middle, last);
    merge(a, first, middle, last);
    copyArray(a,b, first, last);
}

 

The algorithm is simple : Populate an array with random integers, try the algorithm, get execution time of the algorithm ( How many milliseconds to complete ), populate another array with random integers, try another algorithm, get execution time, repeat with larger arrays with different algorithms

Code :

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <ctime>
#include <sys/time.h>
#include <fstream>
#include <math.h>

using namespace std;

int* b;
bool odd;
bool enablePrinting=false;
//Selection Sort
void selectionSort(int* a, int size)
{
    for (int i = 2; i < size; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            if (a[j] < a[j - 1])
            {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}
/////////////////////////////

//Insertion Sort
void insertionSort(int* a, int size)
{
    for (int i = 1;i < size;i++)
    {
		int x = a[i];
		int j = i;
        while (j > 0 && a[j-1] > a[j])
        {
			int temporaryVariable=a[j];
			a[j] = a[j-1];
			a[j-1]=temporaryVariable;
			j --;
        }
        a[j] = x;
    }
}
/////////////////////////////
//Merge Sort
void merge(int* a, int first, int middle, int last)
{
	int j,i0,i1;
    i0 = first;
    i1 = middle;

    // While there are elements in the left or right runs
    
    for (j = first; j < last; j++) {
        // If left run head exists and is <= existing right run head.
        if (i0 < middle && (i1 >= last || a[i0] <= a[i1])){
            b[j] = a[i0];
            i0++;
		}
        else{
            b[j] = a[i1];
            i1++;
		}
    } 
	
}
void copyArray(int* a,int* b, int first, int last)
{
    for(int k = first; k < last; k++)
        a[k] = b[k];
}
void split(int* a, int first, int last)
{
	
    if (last - first<2)
		return;
    int middle = floor((first + last) / 2);
    //cout<<first<<" "<<middle<<" "<<last<<endl;
    split(a, first, middle);
    split(a, middle, last);
    merge(a, first, middle, last);
    copyArray(a,b, first, last);
}

/////////////////////////////
int* populateArray(int size)
{
	b=new int[size];
    int* a = new int[size];
    for (int i = 0;i < size;i++)
    {
        srand(rand()*i);
        a[i] = rand() % 100;
        b[i]=-1;
    }
    return a;
}
void printArray(int* a,int size)
{
    for (int i = 0;i < size;i++)
    {
		if(enablePrinting)
			cout<<a[i]<<"  ";
    }
    if(enablePrinting)
		cout<<endl;
}
long long now()
{
    //LINUX ONLY.
    struct timeval timeNow;
	gettimeofday(&timeNow, NULL);
    return (timeNow.tv_sec * 1000000 + timeNow.tv_usec);
}
int diff(timespec end, timespec start)
{
	timespec temp;
	if ((end.tv_nsec-start.tv_nsec)<0) {
		temp.tv_sec = end.tv_sec-start.tv_sec-1;
		temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
	} else {
		temp.tv_sec = end.tv_sec-start.tv_sec;
		temp.tv_nsec = end.tv_nsec-start.tv_nsec;
	}
	return temp.tv_sec;
}

int main()
{
    int sizes[10] ={10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000};

    long long start, end;

    ofstream CFile ("comparison.csv"); 
    CFile<<"SIZE;Selection;Insertion;Merge"<<endl;
     
    for (int i = 0;i < 10;i++)
    {
        int size = sizes[i];
        
        long long selectionSortTimeSum = 0;    
        long long insertionSortTimeSum = 0;
        long long mergeSortTimeSum = 0;
        
        for (int j = 0;j < 1;j++)
        {
			//==Selection==//
            int* a = populateArray(size);
            
            start = now();
            selectionSort(a, size);
            printArray(a,size);
            end = now();
            
            selectionSortTimeSum= end- start;
            
            //==Merge==//
            a = populateArray(size);
            start = now();
            split(a, 0, size);
            printArray(a,size);
            //NOW LIST IS SORTED ON THE 2ND HALF OF A
            end = now();
            mergeSortTimeSum = end- start;
            //==Insertion==//
            a = populateArray(size);
            start = now();
            insertionSort(a, size);
            printArray(a,size);
            end = now();
            insertionSortTimeSum = end- start;
            
            
        }
        cout << "Selection " << size << " : " << selectionSortTimeSum << endl;
        cout << "Insertion " << size << " : " << insertionSortTimeSum << endl;
        cout << "Merge     " << size << " : " << mergeSortTimeSum << endl;
        CFile<<size<<";"<<selectionSortTimeSum<<";"<<insertionSortTimeSum<<";"<<mergeSortTimeSum<<endl;
        
    }
    return 0 ;
}

N is the number of integers in an unsorted array.

Array Size Selection Sort Time Insertion Sort Time Merge Sort Time
10000 181775 108283 1551
20000 715737 452346 2600
30000 1583254 990002 4032
40000 2746640 1769272 5880
50000 4267589 2812567 6926
60000 6193661 3979912 9602
70000 8561373 5550231 10793
80000 11433324 7513606 12272
90000 14797077 9210755 14594
100000 17865420 11691549 15810