Merge Sort

Merge sort is a divide and conquer based algorithm. Its merge behavior names the algorithm. Algorithm details can be found elsewhere but I’ll give my basic merge-sort implementation here. It starts with dividing the array into two equal sized arrays. Division done until each array only holds an element. But merging procedure is the interesting part of the merge array. It merges 2 arrays into one sorted array.

#include <iostream>
#include <cstring>

using namespace std;

void display(int* arr, size_t size)
{
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << endl;
    }
}

void merge_sort_merge(int* B, size_t size_b, int* C, size_t size_c, int* A, size_t size_a)
{
    int i = 0, j = 0, k = 0;

    while (i < size_b && j < size_c) {
        if (B[i] < C[j]) {
            A[k] = B[i];
            i++;
        }
        else {
            A[k] = C[j];
            j++;
        }
        k++;
    }

    if (i == size_b) {
        memcpy(A+k, C+j, (size_c-j)*sizeof(int));
    }
    else {
        memcpy(A+k, B+i, (size_b-i)*sizeof(int));
    }
}

void merge_sort(int* A, size_t size)
{
    if (size <= 1)
        return;

    int* B = new int[size/2];
    int* C = new int[size-size/2];

    memcpy(B, A, (size/2)*sizeof(int));
    memcpy(C, A+size/2, (size-size/2)*sizeof(int));

    merge_sort(B, size/2);
    merge_sort(C, size-size/2);

    merge_sort_merge(B, size/2, C, size-size/2, A, size);

    delete [] B;
    delete [] C;
}

int main() {
    int A[] = {20,10,30,50,100,60,40,90,80,70};

    display(A, 10);

    cout << endl;

    merge_sort(A, 10);

    display(A, 10);

    return 0;
}

 

Leave a Reply

Fill in your details below or click an icon to log in:

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