Mergesort is a divide by conquer sorting algorithm which emphasise on merging. It is done by divide the input array into the smallest possible arrays, sort the items inside them, and then merge the sorted arrays into an external array recursively.
Mergesort is heavily invested in solving #202203102010.
Analysis
- It will result in \(O(N \log N)\) in worst case.
- The space complexity could be \(O(N)\) which is inefficient.
Attention
-
If
malloc
is used to free the temporary arrays, it will slow down the running time considerably.
Implementation
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd) {
int LeftEnd, NumElements, TmpPos;
LeftEnd = Rpos - 1;
TmpPos = Lpos;
NumElements = RightEnd - Lpos + 1;
while (Lpos <= LeftEnd && Rpos <= RightEnd)
if (A[Lpos] <= A[Rpos])
TmpArray[TmpPos++] = A[Lpos++];
else
TmpArray[TmpPos++] = A[Rpos++];
while (Lpos <= LeftEnd) // Copy rest of the first half
TmpArray[TmpPos++] = A[Lpos++];
while (Rpos <= RightEnd) // Copy rest of the second half
TmpArray[TmpPos++] = A[Rpos++];
for (int i = 0; i < NumElements; i++, RightEnd--) {
A[RightEnd] = TmpArray[RightEnd];
}
}
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right) {
int Center;
if (Left < Right) {
Center = (Left + Right) / 2;
MSort(A, TmpArray, Left, Center);
MSort(A, TmpArray, Center + 1, Right);
Merge(A, TmpArray, Left, Center + 1, Right);
}
}
void Mergesort(ElementType A[], int N) {
ElementType *TmpArray = malloc(N * sizeof(ElementType))
if (TmpArray != NULL) {
MSort(A, TmpArray, 0, N - 1);
free(TmpArray);
} else
FatalError("No space for tmp array!!!");
}