In the merge algorithm of merge sort, I don't understand we have to use auxiliary arrays L, R? Why can't we just keep 2 pointers corresponding which element we're comparing in the 2 subarrays L and R so that the merge-sort algorithm remains inplace?
Thanks.
say you split your array s.th. L uses the first half of the original array, and R uses the second half.
then say that durign merge the first few elements from R are smaller than the smallest in L. If you want to put them in the correct place for the merge result, you will have to overwrite elements from L that have not been processed during the merge step yet.
of course you can make a diferent split. But you can always construct such an (then slightly different) example.
My first post here. Be gentle!
Here's my solution for a simple and easy-to-understand stable in-place merge-sort. I wrote this yesterday. I'm not sure it hasn't been done before, but I've not seen it about, so maybe?
The one drawback to the following in-place merge algorithm can degenerate into O(n²) under certain conditions, but is typically O(n.log₂n) in practice. This degeneracy can be mitigated with certain changes, but I wanted to keep the base algorithm pure in the code sample so it can be easily understood.
Coupled with the O(log₂n) time complexity for the driving merge_sort() function, this presents us with a typical time complexity of O(n.(log₂n)²) overall, and O(n².log₂n) worst case, which is not fantastic, but again with some tweaks, it can be made to almost always run in O(n.(log₂n)²) time, and with its good CPU cache locality it is decent even for n values up to 1M, but it is always going to be slower than quicksort.
// Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)
#include <stddef.h>
#include <stdio.h>
#define swap(x, y) (t=(x), (x)=(y), (y)=t)
// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
int t, *B = &A[an];
size_t pa, pb; // Swap partition pointers within A and B
// Find the portion to swap. We're looking for how much from the
// start of B can swap with the end of A, such that every element
// in A is less than or equal to any element in B. This is quite
// simple when both sub-arrays come at us pre-sorted
for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);
// Now swap last part of A with first part of B according to the
// indicies we found
for (size_t index=pa; index < an; index++)
swap(A[index], B[index-pa]);
// Now merge the two sub-array pairings. We need to check that either array
// didn't wholly swap out the other and cause the remaining portion to be zero
if (pa>0 && (an-pa)>0)
merge_inplace(A, pa, an-pa);
if (pb>0 && (bn-pb)>0)
merge_inplace(B, pb, bn-pb);
} // merge_inplace
// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small. 'n' must
// ALWAYS be 2 or more. It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
size_t m = n/2;
// Sort first and second halves only if the target 'n' will be > 1
if (m > 1)
merge_sort(a, m);
if ((n-m)>1)
merge_sort(a+m, n-m);
// Now merge the two sorted sub-arrays together. We know that since
// n > 1, then both m and n-m MUST be non-zero, and so we will never
// violate the condition of not passing in zero length sub-arrays
merge_inplace(a, m, n-m);
} // merge_sort
// Print an array */
static void
print_array(int a[], size_t size)
{
if (size > 0) {
printf("%d", a[0]);
for (size_t i = 1; i < size; i++)
printf(" %d", a[i]);
}
printf("\n");
} // print_array
// Test driver
int
main()
{
int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
size_t n = sizeof(a) / sizeof(a[0]);
merge_sort(a, n);
print_array(a, n);
return 0;
} // main
If you ever tried to write a merge sort in place, you will soon find out why you can't wen you are merging the 2 sub arraies - you basically need to read from and write to the same range of the array, and it will overwrite each other. Hence we need any auxiliary array:
vector<int> merge_sort(vector<int>& vs, int l, int r, vector<int>& temp)
{
if(l==r) return vs; // recursion must have an end condition
int m = (l+r)/2;
merge_sort(vs, l, m, temp);
merge_sort(vs, m+1, r, temp);
int il = l, ir=m+1, i=l;
while(il <= m && ir <= r)
{
if(vs[il] <= vs[ir])
temp[i++] = vs[il++];
else
temp[i++] = vs[ir++];
}
// copy left over items(only one of below will apply
while(il <= m) temp[i++] = vs[il++];
while(ir <= r) temp[i++] = vs[ir++];
for(i=l; i<=r; ++i) vs[i] = temp[i];
return vs;
}
