What sort in place when two arrays are located?

Question

I am working on this issue . My function prototype

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

In the second part of the function, I know that leftPos in leftPos + (rightPos-leftPos) / 2 and (rightPos-leftPos) / 2 in rightPos are sorted in order.

I tried to think about how I could pretend in place, knowing that the two parts are in order. I could not think of anything. I looked at the merge function merge sort , but uses the output array instead, and not in place.

How do I sort it in place, knowing that both slices are OK?

Note. I thought I could pass in an extra array with the same length as the main array for use as temporary memory, but as I thought, I would need to make Array.Copy after each merge.

Answer 1

On-site merging is possible, but it gets more complicated and doesn't give a big gain in performance. Below is a sample code here . from is your leftPos , to is your rightPos , pivot is your (rightPos-leftPos)/2 , and 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); }