Improving Mergesort. Improvement 3). Use one less copy between input and temp arrays

I am currently working on a project for my algorithms class and am at a bit of a standstill. We were assigned to do improvements to merge sort, that was in the book, by implementing specific changes. I have worked fine through the first 2 changes but the 3'rd one is killer.

Merge sort, the one we are improving, copies the contents of the input array into the temporary array, and then copies the temporary array back into the input array. So it recursively sorts the input array, placing the two sorted halves into the temporary array. And then it merges the two halves in the temporary array together, placing the sorted sequence into the input array as it goes.

The improvement is that this double copying is wasteful can be done without. His hint is that: We can make it so that each call to Merge only copies in one direction, but the calls to Merge alternate the direction.

This is supposedly done by blurring the lines between the original and temporary array.

I am not really looking for code as I am confident that I can code this. I just have no idea what i'm supposed to be doing. The professor is gone for the day so I can't ask him until next week when I have his course again.

Has anyone done something like this before? Or can decipher and put it into laymans terms for me :P

Th开发者_开发知识库e first improvement, simply has it use insertion sort whenever an Array gets small enough that it will benefit greatly, timewise, from doing so.

The second improvement stops allocating two dynamic arrays (the 2 halves that are sorted) and instead allocates 1 array of size n and that is what is used instead of the two dynamic arrays. That's that last one I did. The code for that is :

//#include "InsertionSort.h"
#define INSERTION_CUTOFF 250
#include <limits.h>  // needed for INT_MAX (the sentinel)
void merge3(int* inputArray, int p, int q, int r, int* tempArray)
{
  int i,j,k;
  for (i = p; i <= r; i++)
  {
    tempArray[i] = inputArray[i];
  }
  i = p;
  j = q+1;
  k = p;
  while (i <= q && j <= r)
  {
    if (tempArray[i] <= tempArray[j])
    {
      inputArray[k++] = tempArray[i++];
    }
    else
    {
      inputArray[k++] = tempArray[j++];
    }
  }
}//merge3()

void mergeSort3Helper(int* inputArray, int p, int r, int* tempArray)
{
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int q = (p+r-1)/2;
  mergeSort3Helper(inputArray,p,q,tempArray);
  mergeSort3Helper(inputArray,q+1,r,tempArray);
  merge3(inputArray,p,q,r,tempArray);
}//mergeSort3Helper()

void mergeSort3(int* inputArray, int p, int r)
{
  if (r-p < 1)
  {
    return;
  }
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int* tempArray = malloc((r-p)+1*sizeof(int));
  tempArray[r+1] = INT_MAX;
  mergeSort3Helper(inputArray,p,r,tempArray);
//  This version of merge sort should allocate all the extra space
//  needed for merging just once, at the very beginning, instead of
//  within each call to merge3().
}//mergeSort3()    

---

The algorithm is like this:
A1: 7 0 2 9 5 1 4 3
A2: (uninitialized)

Step 1:
A1 : unchanged
A2: 0 7 2 9 1 5 3 4

Step 2:
A1: 0 2 7 9 1 3 4 5
A2: unchanged

Step 3:
A1: unchanged
A2: 0 1 2 3 4 5 7 9

This involves you copying only one way each time and follows the steps of mergesort. As your professor said, you blur the lines between the work array and the sorted array by alternating which is which, and only copying once things are sorted.

---

I suspect it would be difficult and ultimately unprofitable to avoid all copying. What you want to do instead is to avoid the copy you currently do with each merge.

Your current merge3(inputArray, p,q,r, tempArray) returns the merged result in its original array, which requires a copy; it uses its tempArray buffer only as a resource. In order to do better, you need to modify it to something like merge4(inputArray, p,q,r, outputArray), where the result is returned in the second buffer, not the first.

You will need to change the logic in mergeSort3Helper() to deal with this. One approach requires a comparable interface change, to mergeSort4Helper(inputArray, p,q,r, outputArray), such that it also yields its result in its second buffer. This will require a copy at the lowest (insertion sort) level, and a second copy in the top-level mergeSort4() if you want your final result in the same buffer it came in. However, it eliminates all other unnecessary copies.

Alternately, you could add a boolean parameter to mergeSort4Helper() to indicate whether you want the result returned in the first or second buffer. This value would alternate recursively, resulting in at most one copy, at the lowest level.

A final option might be to do the merging non-recursively, and alternate buffers at each pass. This would also result in at most one copy; however, I would expect the resulting access pattern to be inherently less cache-friendly than the recursive one.