Sorting: Merge Sort
13th January 2006 - By Paradochs
Information
- Order: O(nlog(n))
- Best Case: O(nlog(n))
- Average: O(nlog(n))
- Memory Usage: O(n)
- Stable: Yes
- Comparison Based: Yes
Description (from wikipedia)
Conceptually, merge sort works as follows:
- Divide the unsorted list into two sublists of about half the size
- Sort each of the two sublists
- Merge the two sorted sublists back into one sorted list.
The algorithm was invented by John von Neumann in 1945.
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
MergeSort.h
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:9 Feb 05
File: MergeSort.h
*/
#include <time.h>
class MergeSort {
public:
MergeSort();
MergeSort(int *, int);
~MergeSort();
int * getArray();
int getN();
bool getSorted();
double getTime();
int getIncrements();
void setArray(int *);
void sort();
private:
void setN(int);
void setSorted(bool);
void resetTime();
void resetIncrements();
void MSort(int *, int *, int, int);
void Merge(int *, int *, int, int, int);
int * A;
int * B;
int n;
bool sorted;
double time;
int increments;
};
MergeSort.cpp
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:16 Feb 05
File: MergeSort.cpp
*/
#include "MergeSort.h"
MergeSort::
MergeSort() {
n = 1;
A = new int[n];
B = new int[n];
A[0] = 0;
B[0] = 0;
sorted = true;
resetTime();
resetIncrements();
}
MergeSort::
MergeSort(int * newArray, int N) {
n = N;
A = new int[n];
B = new int[n];
for(int i=0; i<n; i++)
A[i] = newArray[i];
sorted = false;
resetTime();
resetIncrements();
}
MergeSort::
~MergeSort() {
delete(A);
}
int *
MergeSort::
getArray() {
return A;
}
int
MergeSort::
getN() {
return n;
}
bool
MergeSort::
getSorted() {
return sorted;
}
double
MergeSort::
getTime() {
return time;
}
int
MergeSort::
getIncrements() {
return increments;
}
void
MergeSort::
setArray(int * newArray) {
delete(A);
n = sizeof(newArray);
A = new int[n];
B = new int[n];
sorted = false;
}
void
MergeSort::
sort() {
int i = n;
int k;
for(k=0; k<n; k++)
B[k] = A[k];
time_t t1, t2;
t1 = clock();
MSort(A, B, 0, n-1);
t2 = clock();
time = (t2 - t1)/CLOCKS_PER_SEC;
for(k=0; k<i; k++)
A[k] = B[k];
}
void
MergeSort::
MSort(int * source, int * destination, int lower, int upper) {
int mid;
if(increments++, lower < upper) {
mid = (lower + upper) / 2;
MSort(destination, source, lower, mid);
MSort(destination, source, mid+1, upper);
Merge(source, destination, lower, mid, upper);
}
}
void
MergeSort::
Merge(int * source, int * destination, int lower, int mid, int upper) {
int s1 = lower;
int s2 = mid + 1;
int d = lower;
do {
if(increments++, source[s1] < source[s2]) {
destination[d] = source[s1];
s1++;
}
else {
destination[d] = source[s2];
s2++;
}
d++;
} while((increments++, s1 <= mid) && (increments++, s2 <= upper));
if(increments++, s1 > mid)
do {
destination[d] = source[s2];
s2++;
d++;
} while (increments++, s2 <= upper);
else
do {
destination[d] = source[s1];
s1++;
d++;
} while (increments++, s1 <= mid);
}
void
MergeSort::
setN(int newN) {
n = newN;
}
void
MergeSort::
setSorted(bool newSorted) {
sorted = newSorted;
}
void
MergeSort::
resetTime() {
time = 0.0;
}
void
MergeSort::
resetIncrements() {
increments = 0;
}