## Thursday, June 3, 2010

### In place Merge sort

In place merge sort is kinda like shoting your self in the foot before a race.. memory is cheap so the additional movement of data that this thing creates is meaningless. Also this version isnt very efficient because it implements the rotate of the data array via 3 reversal steps.
The alternate is done with a gray counter and a modulas of the counters remainder (ie the greatest common denominator between the total size left and right halves)... clearly Im not about to waste more time on it....

How it Works;
1) divide the list in half
2) perform mergesort on the left and right parts
3) merge the left and right parts
3a) to merge step through the array until a swap with the right is needed
3b) circular rotate the data around in the array by a shift right equal to the size of the right.
3c) set the point to the start of the old left list.

Properties;
Best, Average and Worst case speed is O(nlog(n)).
Memory is 1
In general it is unstable but stable versions do exist.

//compile with g++
#include <iostream>
#include <iomanip>
using namespace std;

void print(int* data, int size);

void reverse(int* data, int size)
{
int temp;
for(int i = 0; i < size/2; i++)
{
temp = data[i];
data[i] = data[size-i-1];
data[size-i-1] = temp;
}
//print(data, size);
}

void inPlaceMergeSort(int* data, int size)
{
if(size < 2)
return;

int mid       = size/2;

inPlaceMergeSort(data,       mid);
inPlaceMergeSort(&data[mid], size - mid);

int left      = 0;
int out       = 0;
while(left != mid)
{
if(data[mid] < data[left])
{
//cout << "orginal:" << left << " " << mid << " " << size << endl;
//print(data, size);
int size_right = size - mid;
reverse(&data[left], mid  - left);
reverse(&data[mid],  size - mid);
reverse(&data[left], size - left);
mid = size - ( mid - left);
}
else
{ left++; }
}
}

//test
#define SIZE 20
#define SCRAMBLE(x, y) ((0xa57b & ~y) + ((0x3829 & x) << 1))

bool check(int data[], int size)
{
for(int i = 1; i < size; i++)
if(data[i] < data[i-1])
{
cout << "FAIL!" << endl;
return false;
}
cout << "PASS" << endl;
return true;
}

void print(int* data, int size)
{
for(int i = 0; i < size; i++)
cout << setw(5) << data[i] << " ";
cout << endl;
}

bool test(int* data, int size)
{
print(data, SIZE);
inPlaceMergeSort(data, SIZE);
print(data, SIZE);
return check(data, SIZE);
}

int main()
{
int data[SIZE];
bool pass = true;

//easy data
data[0] = 1;
for(int i = 0; i < SIZE; i++)
data[i] = SIZE - i;
pass &= test(data, SIZE);

//semi repeated data
data[0] = 1;
for(int i = 1; i < SIZE; i++)
data[i] = SCRAMBLE(i, data[i-1]);
pass &= test(data, SIZE);

//the sort killer
for(int i = 0; i < SIZE; i++)
data[i] = 5;
pass &= test(data, SIZE);

//and some randoms to catch anything i missed
srand ( time(NULL) );

for(int j = 0; j < 100; j++)
{
for(int i = 0; i < SIZE; i++)
data[i] = (int)((float)(j+1)*((float)rand()/(float)RAND_MAX));
pass &= test(data, SIZE);
}

if(pass)
cout << "ALL PASSED" << endl;
else
cout << "FAILED" << endl;
}