Merge Sort Algorithm
The basic idea behide the merge sort algorithm is recursively split the array into two halves till last and sorth them at the end.
// Include files
#include <iostream> // used for cin, cout
#include <conio.h>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
// Global Type Declarations
// Function Prototypes
void instruct (void);
void pause ();
void mergesort(int data[], size_t n);
void merge(int data[], size_t n1, size_t n2);
void display(int data[], size_t n);
//Global Variables - should not be used without good reason.
int main ()
{
// Declaration section
const size_t size = 6;
int num[size];
srand (time (0) );
// Executable section
instruct ();
for (int i = 0; i < size; i++)
num[i] = rand() % 50;
cout << “Unsorted Array” << endl;
display(num,size);
mergesort(num, size);
cout << “\n\nSorted Array” << endl;
display(num, size);
pause ();
return 0;
}
void mergesort(int data[], size_t n)
{
size_t n1;
size_t n2;
if (n > 1)
{
n1 = n / 2;
n2 = n - n1;
mergesort(data, n1);
mergesort((data + n1), n2);
merge(data, n1, n2);
}
}
void merge(int data[], size_t n1, size_t n2)
{
int *temp;
size_t copied = 0;
size_t copied1 = 0;
size_t copied2 = 0;
size_t i;
temp = new int[n1 + n2];
while ((copied1 < n1) && (copied2 < n2))
{
if(data[copied1] < (data + n1)[copied2])
temp[copied++] = data[copied1++];
else
temp[copied++] = (data + n1)[copied2++];
}
while (copied1 < n1)
temp[copied++] = data[copied1++];
while (copied2 < n2)
temp[copied++] = (data + n1)[copied2++];
for (i = 0; i < n1 + n2; ++i)
data[i] = temp[i];
delete [] temp;
}
void display(int data[], size_t n)
{
int row = 0;
for (int i = 0; i < n; i++)
{
cout << data[i] << ” “;
row++ ;
if (row % 10 == 0 )
{
cout << “\n”;
}
}
}
void instruct (void)
{
// Declaration section
// Executable section
}
void pause ()
{
// Declaration section
// Executable section
cout << “\nPress any key to continue…”;
getch();
cout << “\r”;
cout << ” “;
cout << “\r”;
}
/*
Program Output
Unsorted Array
40 16 23 13 23 6
Sorted Array
6 13 16 23 23 40
Press any key to continue…
*/
