Scroll Progress Bar

Merge sort

Merge sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves back together. Here's a C++ implementation of merge sort with comments, along with sample Output:

Program:

    #include <iostream>
    #include 
    
    // Function to merge two sorted subarrays into one sorted array
    void merge(std::vector& arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;
    
        // Create temporary arrays to hold the left and right subarrays
        std::vector leftArr(n1);
        std::vector rightArr(n2);
    
        // Copy data to temporary arrays leftArr[] and rightArr[]
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[middle + 1 + i];
        }
    
        // Merge the two sorted arrays back into arr
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
    
        // Copy the remaining elements of leftArr[], if any
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
    
        // Copy the remaining elements of rightArr[], if any
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    // Merge sort function
    void mergeSort(std::vector& arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = left + (right - left) / 2;
    
            // Recursively sort the first and second halves
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
    
            // Merge the sorted halves
            merge(arr, left, middle, right);
        }
    }
    
    int main() {
        std::vector arr = {64, 34, 25, 12, 22, 11, 90};
    
        std::cout << "Original array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        // Perform merge sort
        mergeSort(arr, 0, arr.size() - 1);
    
        std::cout << "\nSorted array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        return 0;
    }
In this code:
  • merge is a function that merges two sorted subarrays (from left to middle and from middle+1 to right) into one sorted array.
  • mergeSort is the main sorting function that recursively divides the input array into halves, sorts them, and then merges them back together.
  • In the main function, an input array is provided, and both the original and sorted arrays are printed.
Sample Output:

    Original array: 64 34 25 12 22 11 90 
    Sorted array: 11 12 22 25 34 64 90
As shown in the sample output, the input array is successfully sorted in ascending order using the merge sort algorithm.

question

answer

question2

answer2