Mergesort

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!!!");
}
Links to this page
#sorting #algorithm