Merge sorting idea is to sort small parts (pairs) than longer (4 items) and etc, but each next sort phase is MERGE of previous sorted parts. Merging of 2 sorted parts should saves order of items:
1,5 merging 2,3 is 1,2,3,5.
If we avoid recursive implementation then we should generate indexes of all parts (2 items, 4 items...). This sub-task will be done in mergesort() function. Another sub-task is to merge 2 sorted parts into new one, but sorted too. This is implemented in _merge() function, which avoid additional array of result by using of swapping of items: we has 2 arrays with 2 indexes and compare both items (from one array and another, indexed by these 2 indexes). If they need reordering then we swap items. Index of lesser item is incremented (see code below).Main problem is to calculate middle index (for splitting input array into 2 parts for merging). Next formula is used:
mid = lev*2 + pielen*pie;
if (pielen > len || mid > len-1) mid = lastleft;
where lev is the level of pseudo-recursion, pielen is the length of pie (part) = {2, 4, 8...}. len is the length of input array, lastleft is the index of left bound of previous "level". So, we should to get something like this:lev=0 left=0 mid=0 right=2
lev=0 left=2 mid=2 right=4
lev=0 left=4 mid=4 right=6
lev=0 left=6 mid=6 right=8
lev=0 left=8 mid=8 right=10
lev=0 left=10 mid=10 right=12
lev=1 left=0 mid=2 right=4
lev=1 left=4 mid=6 right=8
lev=1 left=8 mid=10 right=12
lev=2 left=0 mid=4 right=8
lev=2 left=8 mid=8 right=12
lev=3 left=0 mid=8 right=12
So, this is the code:
#include <stdio.h>
#include "algutils.h"
template<typename>
static inline void _merge(T *arr, int left, int mid, int right)
{
T tmp, // tmp item needed for inserting if head position on shift
*larr, // left subarray
*rarr; // right subarray
int llen, // length of left subarray
rlen; // length of right subarray
int l, r; // indexes of compared items in left, right subarrays
l = r = 0;
larr = &arr[left];
if (mid==left) {
// When len==2 swapping is more preferable
rarr = &arr[mid+1];
llen = mid - left + 1;
rlen = right - mid - 1;
} else {
// Common case
rarr = &arr[mid];
llen = mid - left;
rlen = right - mid;
}
// Index in left subarray is limited by "right" index
while ((larr+l < rarr+r) && r < rlen) {
if (larr[l] > rarr[r]) {
tmp = rarr[r];
RSHIFT_ARR(larr+l, llen-(l-r), 1);
larr[l] = tmp;
r++;
}
l++;
}
}
template<typename>
int mergsort(T* arr, int len)
{
int lev, // level of "recursion"
pie, // number of subarray (of part)
pielen, // subarray length: 2, 4, 8...
left, right, // bounds (right is not included)
mid, // middle point for splitting - is the same as left bound of subarray but on prev. level
lastleft; // last left index
if (!arr||!len) return (0);
lev = 0;
pielen = 2;
while (pielen < 2*len) {
pie = 0;
do {
left = pie*pielen;
right = left + pielen;
if (right > len) right = len;
mid = lev*2 + pielen*pie;
if (pielen > len || mid > len-1) mid = lastleft; //mid = len-2;
_merge(arr, left, mid, right);
pie++;
} while (right < len-1);
pielen *= 2;
lev++;
lastleft = left;
}
return (1);
}
/*****************************************
main
****************************************/
int main(void)
{
int arr1[] = {10, 19, 1, 2, 10, 450, 6, 7, 8, 100, 120, 121};
mergsort(arr1, sizeofarray(arr1));
PRINTARR(arr1, "%d");
return (0);
}
Macros RSHIFT_ARR() is trivial:
/// Shift array @a ARR of length @a LEN by @a N positions to right
#define RSHIFT_ARR(ARR, LEN, N) do { \
register int _rshift_arr_i_; \
for (_rshift_arr_i_=(N)+(LEN)-1; \
_rshift_arr_i_>(N)-1; \
_rshift_arr_i_--) \
{ \
*((ARR)+_rshift_arr_i_) = *((ARR)+(_rshift_arr_i_-(N))); \
} \
} while (0)
