Merge sort: time limit exceed

Question

Why I am getting time limit exceeded error in sorting array using merge sort algorithm? What is wrong with my code? I have taken an input of 9 elements.

Input: 4 2 1 8 5 9 6 7 0

Output: Time limit exceeded

#include <bits/stdc++.h>

using namespace std;
int a[100];

void merge(int a[], int l, int r, int m) {
    int t[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i <= m)
        t[k++] = a[i++];
    while (j <= r)
        t[k++] = a[j++];
    for (int i = l; i <= r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r) {
    if (l > r)
        return;

    int m = (r + l) / 2;
    msort(a, l, m);
    msort(a, m + 1, r);
    merge(a, l, r, m);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

Answer 1

There are some problems in your code:

• The test for termination in msort() is incorrect: you should stop when the slice has a single element or less. You currently loop forever on slices of 1 element.

  if (l >= r) return;
  

• You should test in main() if the number n of elements read from the user is no greater than 100, the size of the global array a into which you read the elements to be sorted. You should instead use a local array with the proper size or allocate the array from the heap. The temporary array t in merge() might also be too large for automatic allocation. It is more efficient to allocate temporary space once and pass it recursively.

Note also that it is idiomatic in C and C++ to specify array slices with the index of the first element and the index of the element after the last one. This simplifies the code and allows for empty arrays and avoid special cases for unsigned index types.

Here is a modified version with this approach:

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int l, int r, int m, int t[]) {
    int i = l, j = m, k = 0;
    while (i < m && j < r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i < m)
        t[k++] = a[i++];
    while (j < r)
        t[k++] = a[j++];
    for (int i = l; i < r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r, int t[]) {
    if (r - l > 1) {
        int m = l + (r - l) / 2;
        msort(a, l, m, t);
        msort(a, m, r, t);
        merge(a, l, r, m, t);
    }
}

void msort(int a[], int n) {
    if (n > 1) {
        int *t = new int[n];
        msort(a, 0, n, t);
        delete[] t;
    }
}

int main() {
    int n;

    cin >> n;
    if (n <= 0)
        return 1;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete[] a;
    return 0;
}