2

I am working on this question. My function prototype is 

static void Sort(byte[] arr, int leftPos, int rightPos)

In the 2nd part of the function i know leftPos to leftPos + (rightPos-leftPos)/2 and (rightPos-leftPos)/2 to rightPos are sorted in order.

I tried thinking of how i could do an in place sort knowing the two parts are in order. I couldnt think of any. I looked at the merge function on merge sort but it uses an output array rather than in place.

How do i sort it in place knowing both slices are in order?

Note: I was thinking i could pass in a extra array that is the same length as the main array to use as temp memory but the way i thought of would require me to do Array.Copy after each merge.

Community
  • 1
  • 1

1 Answers1

1

In-place merge is possible, but it's complicated and doesn't give much performance gain. Below is some sample code from here. from is your leftPos, to is your rightPos, pivot is your (rightPos-leftPos)/2 and the lengths are the lengths of each half.

void merge(int from, int pivot, int to, int len1, int len2) {
  if (len1 == 0 || len2==0) return;
  if (len1+len2 == 2) {
   if (compare(pivot, from) < 0)
    exchange(pivot, from);
   return;
  }
  int first_cut, second_cut;
  int len11, len22;
  if (len1 > len2) {
   len11=len1/2;
   first_cut = from + len11;
   second_cut = lower(pivot, to, first_cut);
   len22 = second_cut - pivot;
  } else {
   len22 = len2/2;
   second_cut = pivot + len22;
   first_cut = upper(from, pivot, second_cut);
   len11=first_cut - from;
  }
  rotate(first_cut, pivot, second_cut);
  int new_mid=first_cut+len22;
  merge(from, first_cut, new_mid, len11, len22);
  merge(new_mid, second_cut, to, len1 - len11, len2 - len22);
}
moinudin
  • 134,091
  • 45
  • 190
  • 216
  • What is lower and upper btw? rotate.... while looking at this, it appears it is better if i just used a 2nd array and use array.copy. It be much less lines then this + functions missing (all i notice are lower, upper and rotate) –  Jan 13 '11 at 00:03
  • 1
    @acid I quoted the [source](http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html) which defines those functions. I agree though - it's unlikely to be worth the effort as you're adding overhead to keep things in-place. I was just showing you it can be done if necessary. – moinudin Jan 13 '11 at 00:06