#include <iostream>
using namespace std;

void merge(int A[], int start, int mid, int end) {
    int p = start, q = mid + 1;
    int Arr[end - start + 1], k = 0;

    // Merging the two halves into Arr
    while (p <= mid && q <= end) {
        if (A[p] < A[q]) {
            Arr[k++] = A[p++];
        } else {
            Arr[k++] = A[q++];
        }
    }

    // Copy remaining elements from the left half
    while (p <= mid) {
        Arr[k++] = A[p++];
    }

    // Copy remaining elements from the right half
    while (q <= end) {
        Arr[k++] = A[q++];
    }

    // Copy merged elements back to the original array
    for (int i = 0; i < k; i++) {
        A[start + i] = Arr[i];
    }
}

void mergeSort(int A[], int start, int end) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);
        merge(A, start, mid, end);
    }
}

int main() {
    int A[] = {12, 4, 1, 78, 43, 23};
    int n = sizeof(A) / sizeof(A[0]); // Correct size calculation
    mergeSort(A, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl; // New line for better output formatting
    return 0;
}