Tutorial 27

 ---- 27 Merge sort

#include <iostream>

using namespace std;

// Function to merge two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r) {

    int n1 = m - l + 1;

    int n2 = r - m;

    // Create temporary arrays

    int L[n1];

    int R[n2];

    // Copy data to temporary arrays L[] and R[]

    for (int i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (int j = 0; j < n2; j++)

        R[j] = arr[m + 1 + j];

    // Merge the temporary arrays back into arr[l..r]

    int i = 0; // Initial index of first subarray

    int j = 0; // Initial index of second subarray

    int k = l; // Initial index of merged subarray

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    // Copy the remaining elements of L[], if any

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    // Copy the remaining elements of R[], if any

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

// Main function to implement merge sort - Divide

void mergeSort(int arr[], int l, int r)

 {

    if (l < r) {

        // Find the middle point

        int m = l + (r - l) / 2;

        // Sort first and second halves

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

        // Merge the sorted halves

        merge(arr, l, m, r);

    }

}

// Utility function to print an array

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++)

        cout << arr[i] << " ";

    cout << endl;

}

// Driver code

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Given array is: ";

    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "Sorted array is: ";

    printArray(arr, arr_size);

    return 0;

}