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