C++ Online Compiler
Example: Merge Sort using Recursion in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Merge Sort using Recursion #include <iostream> #include <vector> #include <algorithm> // For std::min (optional, could use ternary operator) // Function to merge two sorted subarrays // arr[left...mid] and arr[mid+1...right] void merge(std::vector<int>& arr, int left, int mid, int right) { // Step 1: Calculate sizes of the two subarrays to be merged int n1 = mid - left + 1; int n2 = right - mid; // Step 2: Create temporary arrays for the left and right subarrays std::vector<int> L(n1); std::vector<int> R(n2); // Step 3: Copy data to temporary arrays L[] and R[] for (int i = 0; i < n1; ++i) L[i] = arr[left + i]; for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j]; // Step 4: Merge the temporary arrays back into arr[left...right] int i = 0; // Initial index of first subarray int j = 0; // Initial index of second subarray int k = left; // 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++; } // Step 5: Copy the remaining elements of L[], if any while (i < n1) { arr[k] = L[i]; i++; k++; } // Step 6: Copy the remaining elements of R[], if any while (j < n2) { arr[k] = R[j]; j++; k++; } } // Main function that sorts arr[left...right] using merge() void mergeSort(std::vector<int>& arr, int left, int right) { // Step 1: Base case for recursion - if left >= right, the subarray has 0 or 1 element, which is already sorted if (left < right) { // Step 2: Find the middle point to divide the array into two halves int mid = left + (right - left) / 2; // Avoids potential overflow for large left/right // Step 3: Recursively sort the first half mergeSort(arr, left, mid); // Step 4: Recursively sort the second half mergeSort(arr, mid + 1, right); // Step 5: Merge the sorted halves merge(arr, left, mid, right); } } // Utility function to print an array void printArray(const std::vector<int>& arr) { for (int x : arr) { std::cout << x << " "; } std::cout << std::endl; } int main() { // Step 1: Initialize an unsorted array std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; int arr_size = arr.size(); // Step 2: Print the original array std::cout << "Original array: "; printArray(arr); // Step 3: Call mergeSort to sort the array mergeSort(arr, 0, arr_size - 1); // Step 4: Print the sorted array std::cout << "Sorted array: "; printArray(arr); return 0; }
Output
Clear
ADVERTISEMENTS