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; }

## No comments:

## Post a Comment