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

Answer 1

A couple of things you should try:

1. The object in the vector Order.
   You should prefer to move it rather than copy it.

2. You keep reallocating space for the temporary buffer c.
   Allocate a temporary buffer once and re-use.

3. 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.

4. 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: