Comparing Execution time with Time Complexity in Merge & Quick Sort

Question

I have implemented Merge & Quick Sort in the textbook what I've learned, and it says Time Complexities of each sorts are like this: Merge Sort: O(n.log(n)) / Quick Sort: average O(n.log(n)) and O(n²) in the worst case (if key array is sorted).

So I executed the programs with Two types of Arrays: sorted and random, with different sizes.

Since I wanted to get the Average time, I have tried 10 times per each case.

Here is the code of Merge & Quick Sort:

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

void Merge(vector<int>& s, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = low;
    vector<int> u(s);

    while (i <= mid && j <= high) {
        if (s.at(i) < s.at(j)) {
            u.at(k) = s.at(i);
            i++;
        } else {
            u.at(k) = s.at(j);
            j++;
        }
        k++;
    }
    if (i > mid) {
        for (int a = j; a < high + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    } else {
        for (int a = i; a < mid + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    }
    for (int a = low; a < high + 1; a++)
        s.at(a) = u.at(a);
}
void MergeSort(vector<int>& s, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(s, low, mid);
        MergeSort(s, mid + 1, high);
        Merge(s, low, mid, high);
    }
}

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void Partition(vector<int>& s, int low, int high, int& pvpoint) {
    int j;
    int pvitem;

    pvitem = s.at(low);
    j = low;
    for (int i = low + 1; i <= high; i++) {
        if (s.at(i) < pvitem) {
            j++;
            swap(s.at(i), s.at(j));
        }
        pvpoint = j;
        swap(s.at(low), s.at(pvpoint));
    }
}

void QuickSort(vector<int>& s, int low, int high) {
    int pvpoint;
    if (high > low) {
        Partition(s, low, high, pvpoint);
        QuickSort(s, low, pvpoint - 1);
        QuickSort(s, pvpoint + 1, high);
    }
}

And each of these main() functions are printing the execution times in SORTED, and RANDOM key arrays. you can see the result with adding one of these main functions in Visual Studio(C++):

//Sorted key array
int main() {
    int s;
    for (int i = 1; i < 21; i++) { //Size is from 300 to 6000
        s = i * 300;
        vector<int> Arr(s);
        cout << "N : " << s << "\n";

        //Assign Random numbers to each elements
        Arr.front() = rand() % Arr.size();
        for (int j = 1; j < Arr.size(); j++) { Arr.at(j) = ((737 * Arr.at(j - 1) + 149) % (Arr.size() * 5)); }
        sort(Arr.begin(), Arr.end());

        //QuickSort(Arr, 0, Arr.size() - 1);  <- you can switch using this instead of MergeSort(...) below
        for (int i = 0; i < 10; i++) { //print 10 times of execution time
            clock_t start, end;
            start = clock();
            MergeSort(Arr, 0, Arr.size() - 1);
            end = clock() - start;
            printf("%12.3f  ", (double)end * 1000.0 / CLOCKS_PER_SEC);
        }
        cout << endl;
    }
    return 0;
}

---

//Random key array
int main() {
    int s;
    for (int i = 1; i < 21; i++) {
        s = i * 3000;
        vector<int> Arr(s);
        cout << "N : " << s << "\n";
        for (int i = 0; i < 10; i++) {
            //Assign Random numbers to each elements
            Arr.front() = rand() % Arr.size();
            for (int j = 1; j < Arr.size(); j++) { Arr.at(j) = ((737 * Arr.at(j - 1) + 149) % (Arr.size() * 5)); }

            //QuickSort(Arr, 0, Arr.size() - 1);  <- you can switch using this instead of MergeSort(...) below
            clock_t start, end;
            start = clock();
            MergeSort(Arr, 0, Arr.size() - 1);
            end = clock() - start;
            printf("%12.3f  ", (double)end * 1000.0 / CLOCKS_PER_SEC);
        }
        cout << endl;
    }
    return 0;
}

And the THING is, the result is not matching with their time complexity. for example, Merge sort in(RANDOM Array) size N=3000 prints 20 ms, but size N=60000 prints 1400~1600 ms !! it supposed to print almost 400 ms because Time complexity (Not in worse case) in Quick Sort is O(n.log(n)), isn't it? I want to know what affects to this time and how could I see the printed time that I expected.

Answer 1

You posted the same code in this question: Calculate Execution Times in Sort algorithm and you did not take my answer into account.

Your MergeSort function has a flaw: you duplicate the whole array in merge causing a lot of overhead and quadratic time complexity. This innocent looking definition: vector<int> u(s); defines u as a vector initialized as a copy of s, the full array.

C++ is a very powerful language, often too powerful, littered with traps and pitfalls such as this. It is a very good thing you tried to verify that your program meets the expected performance from the known time complexity of the algorithm. Such a concern is alas too rare.