How do I make my merge sort algorithm more efficient

Question

I'm going to keep this short and sweet, I have an assignment to do for university, and it runs through an online judge, if the time limit is too long (time it takes to run all the inputs, etc. then it hits a time limit)

I have tried bubble sorting, quick sorting, insertion sorting and merge sorting.

Ultimately, merge sorting seems to be one of the stable ones, with a time complexity of Nlog(N), so I'm deciding to stick with this one, my code is the following:

void merge(vector<Order>& orderVector, int low, int high, int mid)
{
    int i, j, k;
    vector<Order> c(orderVector.size(), orderVector.at(0));
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high) {
        if ((orderVector.at(i).selection_time < orderVector.at(j).selection_time) || (orderVector.at(i).selection_time == orderVector.at(j).selection_time && orderVector.at(i).shipping_time < orderVector.at(j).shipping_time)) {
            c.at(k) = orderVector.at(i);
            k++;
            i++;
        }
        else  {
            c.at(k) = orderVector.at(j);
            k++;
            j++;
        }
    }
    while (i <= mid) {
        c.at(k) = orderVector.at(i);
        k++;
        i++;
    }
    while (j <= high) {
        c.at(k) = orderVector.at(j);
        k++;
        j++;
    }
    for (i = low; i < k; i++)  {
        orderVector.at(i) = c.at(i);
    }
}

void sort(vector<Order>& orderVector, int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        sort(orderVector, low, mid);
        sort(orderVector, mid + 1, high);
        merge(orderVector, low, high, mid);
    }
}

I really don't understand what's so inefficient about this, it's literally the standard merge sort code you'd find. I'm referencing orderVector so it makes changes, orderVector is simply just a vector full of "Order" classes, which is just a class with 3 variables (id, selection_time, shipping_time)

What I do is I get the selection_time and check and sort that, once they're sorted I make sure the shipping_time gets sorted only once selection_time is equal, that way it sorts the first value then by the second value.

I think this method is pretty efficient, I have no idea why it does not choose to run efficiently according to this online judge.

The printing code, and the code that adds to the vector (should it be important is the following)

int main(int argc, char *argv[]){
    string data;
    getline(cin, data);
   
    vector<string> data_v = split(data, "; ", numeric_limits<size_t>::max());

    vector<Order> orderVector;

    for(string d : data_v){
        Order *orders = new Order(id, selection, shipping);

        orderVector.push_back(*orders);
    }

    sort(orderVector, 0, orderVector.size() - 1);

    for(long unsigned int i = 0; i < orderVector.size(); i++)
    {
        cout << orderVector.at(i).id << " ";
    }

    cout << endl;
}

please keep in mind i removed the basic template my university gave me so the actual data being put into Order is not shown here, but I don't see how this affects efficiency

To answer some of the questions I might get, c is just the temporary vector, I make it have the same size as the orderVector with class elements inside that I replace anyways — Fernando Goncalves, Sep 14 '22 at 20:17
`Order *orders = new Order(id, selection, shipping);orderVector.push_back(*orders);` -- This is a memory leak. — PaulMcKenzie, Sep 14 '22 at 20:21
@PaulMcKenzie is there any way I could fix this? I'm pretty unsure of how to make it better — Fernando Goncalves, Sep 14 '22 at 20:22
`orderVector.push_back({id, selection, shipping});` -- There is no need for `new`, and even no need to create an `Order` on a separate line. — PaulMcKenzie, Sep 14 '22 at 20:23
If you're just the teeny-tiny bit over the limit, and you've tested the snot out of your code, swap the calls to `at` to `[]`. If possible, stop storing pointers in `orderVector`. Scattering your data through storage can slow a program down dramatically. So dramatically that it often exceeds the cost of copying the whole object. — user4581301, Sep 14 '22 at 20:24
@PaulMcKenzie the thing is, oddly enough it's still hitting a time limit, even that way, I can't tell why it's not working — Fernando Goncalves, Sep 14 '22 at 20:25
@FernandoGoncalves [See this, and look how merge sort is implemented](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). Take that code, and simply call `merge_sort(orderVector.begin(), orderVector.end(), [](auto& o1, auto& o2) { return o1.selection_time < o2.selection_time);});` -- that does a merge sort using nothing but `std::inplace_merge`, basically replacing your function. Do you hit a timeout with that code? — PaulMcKenzie, Sep 14 '22 at 20:27
@user4581301 yeah I am now using Paul's method which is just pass as an array instead of the pointer to the class, still hits time limit it's really odd. — Fernando Goncalves, Sep 14 '22 at 20:27
Merge algorithm doesn't seem to look much like [common reference implementations](https://en.wikipedia.org/wiki/Merge_sort), but that could be because you've combined the merge and sort stages. That said, I don't see any recursion. — user4581301, Sep 14 '22 at 20:31
@FernandoGoncalves -- Basically you can take the code I linked to as a test -- if *that* code gets a timeout, you may be dealing with an unfair time limit. — PaulMcKenzie, Sep 14 '22 at 20:33
`T* obj = new T; v.push_back(*obj);` is an archetypal Java-ism. C++ is not Java. You do not need `new` to create objects in C++. — n. m. could be an AI, Sep 14 '22 at 21:09
Does the online judge only time the sort function or does it time the entire program, including the input and all those couts? — rcgldr, Sep 14 '22 at 23:49
Consider copying the API of `std::merge`: https://en.cppreference.com/w/cpp/algorithm/merge — Ben, Sep 15 '22 at 00:44
@PaulMcKenzie using the merge sort code you gave me, how do I sort by the values inside the classes in the vector rather than the class itself — Fernando Goncalves, Sep 18 '22 at 18:48
@PaulMcKenzie as in, how would I sort it with two values instead of one sorry — Fernando Goncalves, Sep 18 '22 at 19:07
@FernandoGoncalves Look at the code in the comment I made. You pass to it the begin() and end() of the vector, as well as the comparison specification. Your `sort` function just calls `merge_sort`, thus this becomes basically one single line of code. You don't need `low` or `high` for this test, just use exactly what I stated. — PaulMcKenzie, Sep 18 '22 at 19:22
@FernandoGoncalves [This is an example of how it should be used](https://godbolt.org/z/bxjGhzzxE). — PaulMcKenzie, Sep 18 '22 at 20:08

Martin York · Answer 1 · 2022-09-15T00:02:27.803

A couple of things you should try:

The object in the vector Order.
You should prefer to move it rather than copy it.
You keep reallocating space for the temporary buffer c.
Allocate a temporary buffer once and re-use.
Don't use at() when you know the index can not be out of range.
Use operator[] as it does not do the extra work of range checking.
Don't copy back to the original location if you don't need to:

for (i = low; i < k; i++) { orderVector.at(i) = c.at(i); }

Do this part only if needed after the container has been sorted.

As a side note: Simplify this:

if ((orderVector.at(i).selection_time < orderVector.at(j).selection_time) || (orderVector.at(i).selection_time == orderVector.at(j).selection_time && orderVector.at(i).shipping_time < orderVector.at(j).shipping_time)) {

By defining a comparison operator for Order objects (or put it in a function).

As a side note: Don't limit your self to vector. Define your interface in terms of an iterator.

As a side note: Prefer to use standard algorithms rather than writing loops all over the place.

while (j <= high) {
    c.at(k) = orderVector.at(j);
    k++;
    j++;
}
// OR
std::move(iterator_j, iterator_jend, iterator_k);

This can be improved:

for(string d : data_v){
    Order *orders = new Order(id, selection, shipping);

    orderVector.push_back(*orders);
}

Try this:

for(string d : data_v){
    orderVector.emplace_back(id, selection, shipping);
}

You can also ask for a full code review.

Or you can have a look at some other peoples attempts and their code reviews:

How do I make my merge sort algorithm more efficient

1 Answers1