[Algorithm] A new inplace merge algorithm (for merge sort or not)

For the fun I developed an inplace merge algorithm and describe it in a pdf file.
Quentin helps me for the proof.

The PDF can be found here: Inplace-merge-algorithm.

And the related code here:

////////////////////////////////////////////////////////////////
// Author Berenger (Berenger.eu)
// This code proposes a in place merge of two arrays
// and its corresponding merge sort.
// Please refer to the paper to know more
////////////////////////////////////////////////////////////////
#include <cstdio>
#include <cstdlib>
#include <unistd.h>
#include <cstring>
#include <sys/time.h>


// Uncomment the next line to get more output
//#define VERBOSE(V) V;
#ifndef VERBOSE
#define VERBOSE(V)
#endif

////////////////////////////////////////////////////////////////
// Utils functions
////////////////////////////////////////////////////////////////

double GetTime(){
    timeval t;
    gettimeofday(&t, NULL);
    return double(t.tv_sec) + (double(t.tv_usec)/1000000.0);
}

// test if an array is sorted
bool isSorted(const int array[], const int size){
    for(int idx = 1 ; idx < size ; ++idx){
        if(array[idx-1] > array[idx]){
            return false;
        }
    }
    return true;
}

// print an array [index] = value
void print(const int array[], const int size){
    for(int idx = 0 ; idx < size ; ++idx){
        printf("[%d] = %d, ", idx, array[idx]);
    }
    printf("\n");
}

// increment randomly some values in the array
void insertIncRandom(int array[], const int size, const int starValue = 0){
    if(size){
        array[0] = starValue + rand()/(RAND_MAX/5);
        for(int idx = 1 ; idx < size ; ++idx){
            array[idx] = (rand()/(RAND_MAX/5)) + array[idx-1];
        }
    }
}

void insertRandom(int array[], const int size){
    for(int idx = 0 ; idx < size ; ++idx){
        array[idx] = int(size * double(rand())/RAND_MAX);
    }
}

// swap two values in an array
void swap(int array[], const int firstIndex, const int secondIndex){
    register const int swapedValue = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = swapedValue;
}

// swap two values from pointer
void swap(int*const firstValue, int*const secondValue){
    register const int swapedValue = *firstValue;
    *firstValue = *secondValue;
    *secondValue = swapedValue;
}

// get the max of two values
int max(const int firstValue, const int secondeValue){
    return firstValue > secondeValue ? firstValue : secondeValue;
}

// get the PPCM res = v1*c1 = v2*c2
int ppcm(int value1, int value2, int*const coef1, int*const coef2){
    (*coef1) = 1;
    (*coef2) = 1;
    while( value1 * (*coef1) != value2 * (*coef2) ){
        if(value1 * (*coef1) < value2 * (*coef2)){
            ++(*coef1);
        }
        else{
            ++(*coef2);
        }
    }
    return value1 * (*coef1);
}

////////////////////////////////////////////////////////////////
// Reorder functions
////////////////////////////////////////////////////////////////

// Reorder an array in place with no extra moves :
// if we have [0 1 2 3 4 5 ; A B C]
// it creates [A B C ; 0 1 2 3 4 5]
void reorderRolling(int array[], const int lengthLeftPart, const int totalSize){
    const int lengthRightPart = totalSize - lengthLeftPart;
    // if one of the partitions has 0 size
    if(lengthLeftPart == 0 || lengthRightPart == 0){
        // do nothing
    }
    // if partitions have the same size
    else if(lengthLeftPart == lengthRightPart){
        for(int idx = 0 ; idx < lengthLeftPart ; ++idx){
            swap(array, idx, idx + lengthLeftPart);
        }
    }
    else {
        // Otherwise exchange values of the partition
        int coefLeft  = 0;
        int coefRight = 0;
        // get the ppcm
        const int ppc = ppcm(lengthLeftPart, lengthRightPart, &coefLeft, &coefRight);
        // this is "t" in the attached repport
        const int end = lengthLeftPart / coefRight;
        // we need to do end cycle
        for(int idx = 0 ; idx < end ; idx += 1){
            // store the first value
            int value = array[idx];
            // keep track of the first index to know when the cycle is over
            int idxToMove = idx;
            do{
                // While we have to do move to right
                while(idxToMove + lengthRightPart < totalSize){
                    idxToMove += lengthRightPart;
                    swap(&array[idxToMove], &value);
                }
                // while we have to do move to the left
                while(0 <= idxToMove - lengthLeftPart){
                    idxToMove -= lengthLeftPart;
                    swap(&array[idxToMove], &value);
                }
                // the cycle is over when we go back to the first index
            }while(idxToMove != idx);
        }
    }
}

// Reorder an array in place with extra moves :
// if we have [0 1 2 3 4 5 ; A B C]
// it creates [A B C ; 0 1 2 3 4 5]
void reorderShifting(int array[], const int lengthLeftPart, const int totalSize){
    const int lengthRightPart = totalSize - lengthLeftPart;
    // if one of the size is zero just return
    if(lengthLeftPart == 0 || lengthRightPart == 0){
        // do nothing
    }

    // size of the partitions at first iteration
    int workingLeftLength  = lengthLeftPart;
    int workingRightLength = lengthRightPart;
    // while the partitions have different sizes and none of them are null
    while(workingLeftLength != workingRightLength && workingLeftLength && workingRightLength){
        // if the left partition is the smallest
        if(workingLeftLength < workingRightLength){
            // move the left parition in the correct place
            for(int idx = 0 ; idx < workingLeftLength ; ++idx){
                swap(array, idx, idx + workingRightLength);
            }
            // the new left partition is now the values that have been swaped
            workingRightLength = workingRightLength - workingLeftLength;
            //workingLeftLength = workingLeftLength;
        }
        // if right partition is the smallest
        else{
            // move the right partition in the correct place
            for(int idx = 0 ; idx < workingRightLength ; ++idx){
                swap(array, idx, idx + workingLeftLength);
            }
            // shift the pointer to skip the correct values
            array = (array + workingRightLength);
            // the new left partition is the previous right minus the swaped values
            //workingRightLength = workingRightLength;
            workingLeftLength  = workingLeftLength - workingRightLength;
        }
    }
    // if partitions have the same size
    for(int idx = 0 ; idx < workingLeftLength ; ++idx){
        swap(array, idx, idx + workingLeftLength);
    }
}

////////////////////////////////////////////////////////////////
// Merge functions
////////////////////////////////////////////////////////////////

void mergeInPlace(int array[], const int sizeArray, const int centerPosition ){
    int idxLeft   = 0;
    int idxRight  = centerPosition;

    // Skip left small values
    // case: some values of A are smaller than the first of B
    while( idxLeft < centerPosition && array[idxLeft] <= array[idxRight] ){
        ++idxLeft;
    }
    // Where to store left values
    int idxBuffer = centerPosition;
    // While there are left values && there are right values
    while(idxLeft < idxRight &&  idxRight < sizeArray){
        // if the first value of A is smaller than the first of B
        // we know this test will be false the first time
        if(idxBuffer != idxRight && array[idxBuffer] <= array[idxRight]){
            int offsetPosition = idxBuffer;
            // while values from A are smaller
            while(idxLeft < idxBuffer && offsetPosition < idxRight &&
                  array[offsetPosition] <= array[idxRight] ){
                swap(array, idxLeft++, offsetPosition++ );
            }
            // if the values in the buffer have not all moved
            if(offsetPosition != idxRight){
                // We are in P4, we need to go back in P3
                reorderRolling(array + idxBuffer, offsetPosition - idxBuffer, idxRight - idxBuffer);
                //reorderShifting(array + idxBuffer, offsetPosition - idxBuffer, idxRight - idxBuffer);
            }
            // all the value of A'' have been moved
            if( idxLeft == idxBuffer ){
                // the buffer becomes the new A
                idxBuffer = idxRight;
                // we move the pointer as long as values from A are smaller
                while( idxLeft < idxBuffer && array[idxLeft] <= array[idxRight] ){
                    ++idxLeft;
                }
            }
        }
        else{
            // The value we have to compare to is the first of A'' or the first from the buffer
            const int leftSmallValue = (idxBuffer == idxRight ? array[idxLeft] : array[idxBuffer]);
            // Swap B and A values
            while( idxLeft < idxBuffer && idxRight < sizeArray
                   && array[idxRight] <= leftSmallValue ){
                swap(array, idxLeft++, idxRight++ );
            }
            // If we have moved all the values of A
            if(idxLeft == idxBuffer){
                // A is now the buffer
                idxBuffer = idxRight;
                // Move the pointer as long as A is smaller
                while( idxLeft < idxBuffer && array[idxLeft] <= array[idxRight] ){
                    ++idxLeft;
                }
            }
        }
    }
    // it is over because no more right values && there are values between left and buffer
    if(idxLeft != idxRight && idxLeft != idxBuffer){
        reorderRolling(array + idxLeft, idxBuffer - idxLeft, idxRight - idxLeft);
        //reorderShifting(array + idxLeft, idxBuffer - idxLeft, idxRight - idxLeft);
    }
}

////////////////////////////////////////////////////////////////
// Merge sorts
////////////////////////////////////////////////////////////////

void inPlaceMergeSort(int array[], const int Size){
    for(int sizeOfPartitions = 1 ; sizeOfPartitions < Size ; sizeOfPartitions *= 2){
        for(int startingIdx = 0 ; (startingIdx+sizeOfPartitions) < Size ; startingIdx += (sizeOfPartitions*2)){
            int sizeOfSecondPartiton = sizeOfPartitions;
            if((startingIdx + sizeOfSecondPartiton + sizeOfPartitions) > Size) sizeOfSecondPartiton = Size - (startingIdx + sizeOfPartitions);
            VERBOSE(printf("Before startingIdx = %d sizeOfSecondPartiton = %d sizeOfPartitions = %d\n", startingIdx, sizeOfSecondPartiton, sizeOfPartitions));
            VERBOSE(print(array, Size));
            mergeInPlace(&array[startingIdx], (sizeOfPartitions+sizeOfSecondPartiton), sizeOfPartitions);
            VERBOSE(printf("After\n"));
            VERBOSE(print(array, Size));
        }
    }
}

////////////////////////////////////////////////////////////////
// Test functions functions
////////////////////////////////////////////////////////////////

// test the reorder function
// it creates two sorted arrays A & B
// with B(end) < A(0)
// So after reordeing the result has to be sorted
void testReorder(){
    // from 4 to 50
    for( int Size = 4 ; Size < 50 ; ++Size){
        int*const array = new int[Size];
        // Middle from 0 to size
        for(int middle = 0 ; middle < Size ; ++middle){
            printf("[Test] Size %d middle %d\n",Size, middle);

            insertIncRandom(array+middle, Size-middle);
            insertIncRandom(array, middle, array[Size-1]);

            VERBOSE(printf("First part is sorted %s\n", isSorted(array,middle)?"True":"False"));
            VERBOSE(print(array,middle));
            VERBOSE(printf("Second part is sorted %s\n", isSorted(array+middle,Size-middle)?"True":"False"));
            VERBOSE(print(array + middle,Size-middle));

            //reorderRolling(array,middle,Size);
            reorderShifting(array,middle,Size);

            VERBOSE(printf("Finaly is sorted %s\n", isSorted(array,Size)?"True":"False"));
            VERBOSE(print(array,Size));
            if( !isSorted(array,Size) ){
                printf("Error, no sorted!\n");
                print(array,Size);
                delete[] array;
                exit(0);
            }
        }

        delete[] array;
    }
}

// Test the merge function by generating two
// random already sorted array so the result
// has to be the union sorted of the inputs
void testMerge(){
    for(int Size = 1 ; Size < 100 ; ++Size){
        int*const array = new int[Size];
        for(int middle = 0 ; middle <= Size ; ++middle){
            printf("[Test] Size %d middle %d\n",Size, middle);

            insertIncRandom(array, middle);
            insertIncRandom(array+middle, Size-middle);

            VERBOSE(printf("First part is sorted %s\n", isSorted(array,middle)?"True":"False"));
            VERBOSE(printf("Second part is sorted %s\n", isSorted(array+middle,Size-middle)?"True":"False"));

            mergeInPlace(array,Size,middle);

            VERBOSE(printf("Finaly is sorted %s\n", isSorted(array,Size)?"True":"False"));
            VERBOSE(print(array,Size));
            if( !isSorted(array,Size) ){
                printf("Error, no sorted!\n");
                print(array,Size);
                delete[] array;
                exit(0);
            }
        }
        delete[] array;
    }
}

// Test to sort using merge
void testSort(){
    const int Size = 100000;
    printf("Test Sort Merge with Size = %d\n", Size);
    // Create array
    int*const array = new int[Size];
    // Insert Random values
    insertRandom(array, Size);

    // Sort and get elapsed time
    const double begin = GetTime();
    inPlaceMergeSort(array, Size);
    const double end = GetTime();
    // Check if sorted
    if( !isSorted(array,Size) ){
        printf("Error, no sorted!\n");
    }
    else{
        printf("Ok is sorted!\n");
    }
    printf("Time %e\n", end-begin);

    delete[] array;
}

// Compare big merge direct and undirect
void testTime(){
    const int MaxSize = 1000000;

    printf("# Size \tMerge \tExternal\n");

    for(int Size = 10 ; Size <= MaxSize ; Size *= 10){
        int*const array = new int[Size];

        double totalMerge    = 0;
        double totalExternal = 0;

        for(int idxMiddle = 0 ; idxMiddle < 3 ; ++idxMiddle){
            const int middle = (idxMiddle+1)*(Size/4);
            {
                srand(0);
                insertIncRandom(array, middle);
                insertIncRandom(array+middle, Size-middle);

                const double begin = GetTime();
                mergeInPlace(array,Size,middle);
                const double end = GetTime();

                totalMerge += end-begin;
                const bool valide = isSorted(array,Size);
                VERBOSE(printf("Time taken %lf s (Sorted %s)\n", end-begin, valide?"True":"False"));
                if(!valide){
                    exit(99);
                }
            }

            {
                srand(0);
                insertIncRandom(array, middle);
                insertIncRandom(array+middle, Size-middle);

                const double begin = GetTime();
                {
                    int*const arrayTemp = new int[Size];
                    memcpy(arrayTemp,array,sizeof(int)*Size);

                    int idx = 0;
                    int idx1 = 0, idx2 = middle;
                    while(idx1 < middle && idx2 < Size){
                        if(arrayTemp[idx1] < arrayTemp[idx2]) array[idx++] = arrayTemp[idx1++];
                        else array[idx++] = arrayTemp[idx2++];
                    }
                    while(idx1 < middle){
                        array[idx++] = arrayTemp[idx1++];
                    }
                    while(idx2 < Size){
                        array[idx++] = arrayTemp[idx2++];
                    }

                    delete[] arrayTemp;
                }
                const double end = GetTime();
                totalExternal += (end-begin);
                const bool valide = isSorted(array,Size);
                VERBOSE(printf("Time taken %lf s (Sorted %s)\n", end-begin, valide?"True":"False"));
                if(!valide){
                    exit(99);
                }
            }
        }

        printf("%d \t%e \t%e\n", Size, totalMerge/3.0, totalExternal/3.0);
        fflush(stdout);

        delete[] array;
    }
}

////////////////////////////////////////////////////////////////
// Main runs test functions
////////////////////////////////////////////////////////////////

int main(int argc, char** argv){
    if(argc == 2 && strcmp(argv[1],"-reorder") == 0){
        testReorder();
    }
    else if(argc == 2 && strcmp(argv[1],"-merge") == 0){
        testMerge();
    }
    else if(argc == 2 && strcmp(argv[1],"-time") == 0){
        testTime();
    }
    else if(argc == 2 && strcmp(argv[1],"-sort") == 0){
        testSort();
    }
    else{
        printf("[Help] %s [-reorder;-merge;-time;-sort]\n", argv[0]);
        return 1;
    }
    return 0;
}