C++ Online Compiler
Example: Merge Sort using Divide and Conquer in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Merge Sort using Divide and Conquer #include <iostream> #include <vector> // Using vector for dynamic array behavior #include <algorithm> // For std::copy // Function to merge two sorted subarrays void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; // Create temporary vectors for left and right halves std::vector<int> L(n1); std::vector<int> R(n2); // Copy data to temporary vectors 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]; // Merge the temporary vectors 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++; } // 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 that implements Merge Sort void mergeSort(std::vector<int>& arr, int left, int right) { // Base case: if the subarray has 0 or 1 element, it's already sorted if (left >= right) { return; } // Find the middle point to divide the array into two halves int mid = left + (right - left) / 2; // Recursively sort the first half mergeSort(arr, left, mid); // Recursively sort the second half mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } // Utility function to print the 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 << "Given array is: "; 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 is: "; printArray(arr); return 0; }
Output
Clear
ADVERTISEMENTS