Merge Sort Code Binary & Ternary

Merge Sort Code Binary & Ternary:


Binary Mergesort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>

#define SIZE 10000
long A[SIZE];
/*
 * Divides The array to Sub arrays until only one element is left
 * Then calls Merge function on each sub arrays
 */

void Merge(unsigned long front, unsigned long mid, unsigned long rear){
    /*
     * Get size of the left sub array
     */
    unsigned long n1 = mid-front+1;

    /*
     * Get size of the right sub array
     */
    unsigned long n2 = rear - mid;

    /*
     * Declare left and right sub array with 1 more than original size to store INFINITY
     */
    long *L = new long[n1 + 1];
    long *R = new long[n2 + 1];

    /*
     * Copy elements of given array to Left sub array
     */
    register unsigned long i = 0;
    for(; i<n1; ++i){
        L[i] = A[front+i];
    }

    /*
     * Copy elements of given array to Right sub array
     */
    register unsigned long j = 0;
    for(j=0; j<n2; ++j){
        R[j] = A[mid+1+j];
    }

    /*
     * Set the last element in array to an infinitely big value
     */
    L[n1] = LONG_MAX;
    R[n2] = LONG_MAX;

    /*
     * Reset both sub array index
     */
    i = 0;
    j = 0;

    /*
     * Merge:
     * Compare left and right sub array
     * Merge the smaller element back to original array
     */
    register unsigned long k = front;
    for(; k<=rear; ++k){
        /*
         * The left array item is smaller
         * Increment sub array counter to check for next element
         */
        if(L[i] <= R[j]){
            A[k] = L[i];
            ++i;
        }
        /*
         * The right array item is smaller
         * Increment sub array counter to check for next element
         */
        else{
            A[k] = R[j];
            ++j;
        }
    }
}

void Mergesort(unsigned long front, unsigned long rear){
    if(front < rear){
        /*
         * Calculate the mid point of the given array
         */
        unsigned long mid = (rear+front) >> 1;

        /*
         * Divide given array by recursively sending left half of original array
         */
        Mergesort(front, mid);

        /*
         * Divide given array by recursively sending right half of original array
         */
        Mergesort(mid+1, rear);

        /*
         * Merge the sub arrays
         */
        Merge(front, mid, rear);
    }
}

int main(){
    long i=0, j=0, temp;

    //variables needed to record time
    clock_t begin, end;

    double time_spent;

    srand(time(NULL));
    for(; i<SIZE; ++i){
        A[i] = rand() % SIZE;
    }

    begin = clock();

    Mergesort(0, SIZE-1);

    end = clock();
    time_spent = (double) (end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i){
        printf("%ld ", A[i]);
    }

    printf("\nTime elapsed: %lf\n", time_spent);

    return 0;
}

 

Ternary Mergesort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>

#define SIZE 500
long A[SIZE];
/*
 * Divides The array to Sub arrays until only one element is left
 * Then calls Merge function on each sub arrays
 */

void Merge(unsigned long front, unsigned long mid1, unsigned long mid2, unsigned long rear){
    /*
     * Get size of the left sub array
     */
    unsigned long n1 = mid1 - front + 1;

    /*
     * Get size of the right sub array
     */
    unsigned long n2 = mid2 - mid1;
    unsigned long n3 = rear - mid2;

    /*
     * Declare left and right sub array with 1 more than original size to store INFINITY
     */
    long *L = new long[n1 + 1];
    long *R = new long[n2 + 1];
    long *X = new long[n3 + 1];

    /*
     * Copy elements of given array to 1st sub array
     */
    register unsigned long i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    /*
     * Copy elements of given array to 2nd sub array
     */
    register unsigned long j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid1 + 1 + j];

    /*
     * Copy elements of given array to 3rd sub array
     */
    register unsigned long p = 0;
    for(; p < n3; ++p)
        X[p] = A[mid2 + 1 + p];

    /*
     * Set the last element in array to an infinitely big value
     */
    L[n1] = LONG_MAX;
    R[n2] = LONG_MAX;
    X[n3] = LONG_MAX;

    /*
     * Reset both sub array index
     */
    i = 0;
    j = 0;
    p = 0;

    /*
     * Merge:
     * Compare left and right sub array
     * Merge the smaller element back to original array
     */
    register unsigned long k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j] && L[i] <= X[p])
            A[k] = L[i++];
        else if(R[j] <= X[p])
            A[k] = R[j++];
        else
            A[k] = X[p++];
    }
}

void Mergesort(unsigned long front, unsigned long rear){
    if(front < rear){
        /*
         * Calculate the mid point of the given array
         */
        unsigned long dist = (rear - front + 1) / 3;
        unsigned long mid1 = front + dist;
        unsigned long mid2 = mid1 + dist;

        /*
         * Divide given array recursively by recursively breaking into three parts
         */
        Mergesort(front, mid1);
        Mergesort(mid1 + 1, mid2);
        Mergesort(mid2 + 1, rear);

        /*
         * Merge the sub arrays
         */
        Merge(front, mid1, mid2, rear);
    }
}

int main(){
    register unsigned long i = 0, j = 0;

    //variables needed to record time
    clock_t begin, end;

    double time_spent;

    srand(time(NULL));
    for(; i < SIZE; ++i)
        A[i] = rand() % SIZE;

    begin = clock();

    Mergesort(0, SIZE-1);

    end = clock();
    time_spent = (double) (end - begin) / CLOCKS_PER_SEC;

    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\nTime elapsed: %lf\n", time_spent);

    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s