How can I optimize this mergesort?

Question

In main:

for(int i = 1; i < upto; i *= 2)
    {  for(int j = 0; j < (upto - i); j += (2*i))
       {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;
          mymerge(&(array[j]), i, end2); }  }

Merge:

void mymerge(people  *arr, int end1, int end2){
  int i = 0;
  int j = end1;
  int k = 0;
  people * temp = new people[end2];

  while(i < end1 && j < end2){
    if(arr[i].lname < arr[j].lname){
        temp[k] = arr[i];
        i += 1;
    }else if(arr[i].lname > arr[j].lname){
        temp[k] = arr[j];
        j += 1;
    }else if(arr[i].fname < arr[j].fname){
        temp[k] = arr[i];
        i += 1;
    }else if(arr[i].fname > arr[j].fname){
        temp[k] = arr[j];
        j += 1;
    }else if(arr[i].dob < arr[j].dob){
        temp[k] = arr[i];
        i += 1;
    }else if(arr[i].dob >= arr[j].dob){
        temp[k] = arr[j];
        j += 1; }

   k += 1;
 }

  while( i < end1){
    temp[k] = arr[i];
    i +=1; k +=1; }

  while(j < end2){
    temp[k] = arr[j];
    j += 1; k += 1; }

  for(int c = 0; c < end2; c += 1)
    arr[c] = temp[c];

  delete [] temp;
}

Would a recursive or iterative approach improve run time? Is there a better way to use pointers? This would be for an array that is not likely to be in any partially sorted order.

Answer 1

First you should define your ordering separately from your merge:

bool operator<(people const& lhs, people const& rhs)
{
    if (lhs.lname < rhs.lname)  {return true;}
    if (lhs.lname > rhs.lname)  {return false;}

    // lhs.lname == rhs.lname 
    if (lhs.fname < rhs.fname)  {return true;}
    if (lhs.fname > rhs.fname)  {return false;}

    // lhs.lname == rhs.lname  && lhs.fname == rhs.fname
    if (lhs.dob < rhs.dob)      {return true;}

    // Optimize away the last test.
    //if (lhs.dob > rhs.dob)      {return false;}

    return false;
}

Incrementing by one can be done with the operator++

j += 1;
// Easier to write as:
++j;

Or you can do it in-place with:

temp[k] = arr[i];
i += 1;
// Easier to write as
temp[k] = arr[i++];

Using new/delete is a bad idea. It makes you do all the memory management. It is better to use classes that do it all for you. In your case std::vector is a better choice for memory management of arrays

people * temp = new people[end2];
....
delete [] temp;
// Better to use std::vector
std::vector<people>  temp(end2);
....

Prefer to use standard algorithms rather than manual loops.

  for(int c = 0; c < end2; c += 1) {
    arr[c] = temp[c];
  }
  // Use std::copy
  std::copy(temp.begin(), temp.end(), arr);

If you are copying something and not going to use the original again. Then try and move the object to the destination rather than copying it.

  temp[k] = arr[i];
  // Prefer to move rather than copy
  // if you are not going to use the value at arr[i] again.
  temp[k] = std::move(arr[i]);

  // Note this assumes you have defined move constructor and move assignment operator
  // for the class people. If you have not defined these operations then it will
  // default to use the normal copy versions.

Now your merge becomes more readable:

void mymerge(people  *arr, int end1, int end2)
{
  int i = 0;
  int j = end1;
  std::vector<people>  temp;
  temp.reserve(end2);

  while(i < end1 && j < end2)
  {
      people&  src =  (arr[i] < arr[j])
                         ? arr[i++]
                         : arr[j++];
      temp.emplace_back(std::move(src));
  }

  std::move(&arr[i], &arr[end1], std::back_inserter(temp));
  std::move(&arr[j], &arr[end2], std::back_inserter(temp));

  std::move(temp.begin(), temp.end(), arr);
}

Now that I have cleaned up the mymerge() function I can understand what you are doing and it looks like it should work. But it requires the input sections to be already pre-sorted. I am not sure how your double loop in main() achieves this.

Answer 2

for(int i = 1; i < upto; i *= 2)
    {  for(int j = 0; j < (upto - i); j += (2*i))
       {  int end2 = (2*i < (upto - j)) ? 2*i : upto - j;
          mymerge(&(array[j]), i, end2); }  }

I'd like to know how upto is defined here. Is it the size of array? Calling it size or count might make this clearer.

This is a weird format. Here you always put your { on a new line and then put the code after it on the same line. Elsewhere you put your { on the same line and put the code after it on a new line.

}else if(arr[i].dob >= arr[j].dob){
    temp[k] = arr[j];
    j += 1; }

Again, I have trouble following the rules around your formatting. On one line, you start your } on a new line and then later you put it at the end of a line. By doing this you make it hard to scan the code quickly. The read has to check each line to see if there are any { or } on it. It's much easier if they are consistently in the same place so that the reader can follow the structure quickly.

There are three main formats:

Always a new line (BSD style)

if ( true )
{
    // code here
}
else
{
    // more code
}

Always close alone on a new line (half cuddled)

if ( true ) {
    // code here
}
else {
    // more code
}

Always share if you can (K&R)

if ( true ) {
    // code here
} else {
    // more code
}

Most of the code that you'll be reading will follow one of these rules. If your code does as well, then it's going to be much easier for people to follow. We'll already know the rules. I prefer the last version, but there are arguments for and against each.

I also prefer to have spaces between almost all tokens. Note that I write if ( rather than if(. This helps separate things like an if from function calls. It also makes it easier to see the if as it is separate from the opening parenthesis and the first token of the expression. Your format has things like if(arr[i].dob which one has to read moderately thoroughly to see what goes with what.

people * temp = new people[end2];

You redo this for each call to your helper function. Better would be to do this outside the function and reuse the array for each call. You may only be using \$O(n)\$ memory at any time, but you are doing \$O(n \log n)\$ memory allocations. You could do just one (and you have to do that one anyway to do the last merge).

Note that using a standard data type (e.g. std::vector) and letting C++ manage the memory for you should do much the same thing. A smart enough compiler could allocate the memory ahead of time and just do one. If you're doing it manually, try to be at least as smart as the compiler might be.

You ask about iterative and recursive solutions. A purely iterative solution with no function calls is potentially faster, but a good compiler should optimize most of that away. If speed is that important to you, profile both solutions and see if there is a significant difference.

Unless the compiler can optimize out the recursion, a recursive solution will generally be the slowest. Each function call requires the program to save the current state of the world on the stack. Doing so recursively means that you would have to maintain up to \$O(\log n)\$ function calls at any one time. The point of recursion is generally to improve elegance and readability rather than performance.

I won't cover it again, but I agree with Loki Astari's answer on using the < and ++ operators. That would also make it easier to run this same sort with std:sort which is proven correct (less chance of bugs) and might be more efficient. At least it's a possibility worth profiling.

As a side issue, I usually do sorting like this in the database. This is a relatively straightforward three column index in a database. Then sorts are done via insertion sort at write time rather than sorting all the data at read time. You don't post the rest of the code, so it's not clear to me why you are not doing this in the database.

Answer 3

That double for looks like someone is trying to be very clever and compact. no need for that:

for(int subArrayLength = 1; subArrayLength < count; subArrayLength *= 2) {
    for(int j = 0; j < (count- subArrayLength); j += (2*subArrayLength)) {
        int remainingLength = 2*subArrayLength;
        if(remainingLength > count - j)
             remainingLength = count- j; 

        mymerge(&(array[j]), subArrayLength, remainingLength); 
    }  
}

This immediately makes it much clearer how the double for loop works.