Mergesort
In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
#include<stdio.h>
#define SIZE 16
void MergeSort(int destA[SIZE], int iBegin, int iEnd, int sourceB[SIZE]);
void Merge(int destB[SIZE], int iBegin, int iMiddle, int iEnd,int sourceA[SIZE]);
void CopyArray(int destB[SIZE], int iBegin, int iEnd, int sourceA[SIZE]);
void PrintArray(int A[SIZE], int iBegin, int iEnd);
int main()
{
int A[SIZE] = {88,52,32,65,23,21,2,66,90,8,10,3,11,5,70,66};
int B[SIZE];
//int i;
PrintArray(A, 0, SIZE);
// Array A[] has the items to sort; array B[] is a work array.
CopyArray(B, 0, SIZE, A); // duplicate array A[] into B[]
MergeSort(A, 0, SIZE, B); // sort data from B[] into A[]
// PrintArray(A, 0, SIZE);
return 0;
}
// Sort the given run of array B[] using array A[] as a source.
// iBegin is inclusive; iEnd is exclusive (B[iEnd] is not in the set).
void MergeSort(int destA[SIZE], int iBegin, int iEnd, int sourceB[SIZE])
{
int iMiddle;
if(iEnd - iBegin > 1) // if run size == 1
{ // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
MergeSort(sourceB, iBegin, iMiddle, destA); // sort the left run
MergeSort(sourceB, iMiddle, iEnd, destA); // sort the right run
// merge the resulting runs from array B[] into A[]
Merge(destA, iBegin, iMiddle, iEnd, sourceB); // merge from B to A
}
PrintArray(destA, iBegin, iEnd);
}
// Left source half is sourceA[iBegin:iMiddle-1].
// Right source half is sourceA[iMiddle:iEnd-1 ].
// Result is destB[ iBegin:iEnd-1 ].
void Merge(int destB[SIZE], int iBegin, int iMiddle, int iEnd, int sourceA[SIZE])
{
int i,j,k;
i = iBegin;
j = iMiddle;
// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++)
{
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || sourceA[i] <= sourceA[j]))
{
destB[k] = sourceA[i];
i = i + 1;
}
else
{
destB[k] = sourceA[j];
j = j + 1;
}
}
}
void CopyArray(int destB[SIZE], int iBegin, int iEnd, int sourceA[SIZE])
{
int k;
for(k = iBegin; k < iEnd; k++)
destB[k] = sourceA[k];
}
void PrintArray(int A[SIZE], int iBegin, int iEnd)
{
int i;
for(i=0;i<iBegin;i++)
printf(" ");
for(i=iBegin;i<iEnd;i++)
printf("%5d",A[i]);
printf("\n\n");
}
stdout
88 52 32 65 23 21 2 66 90 8 10 3 11 5 70 66
88
52
52 88
32
65
32 65
32 52 65 88
23
21
21 23
2
66
2 66
2 21 23 66
2 21 23 32 52 65 66 88
90
8
8 90
10
3
3 10
3 8 10 90
11
5
5 11
70
66
66 70
5 11 66 70
3 5 8 10 11 66 70 90
2 3 5 8 10 11 21 23 32 52 65 66 66 70 88 90
note:
