C++ Online Compiler
Example: Merge Sort with User Input in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Merge Sort with User Input #include <iostream> // For input/output operations #include <vector> // For dynamic array (vector) // Function to merge two sorted sub-arrays void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; // Size of the left sub-array int n2 = right - mid; // Size of the right sub-array // Create temporary arrays std::vector<int> L(n1); std::vector<int> R(n2); // 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]; // Merge the temporary arrays back into arr[left...right] int i = 0; // Initial index of first sub-array int j = 0; // Initial index of second sub-array int k = left; // Initial index of merged sub-array 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++; } } // Function to perform Merge Sort void mergeSort(std::vector<int>& arr, int left, int right) { if (left >= right) { // Base case: array with 0 or 1 element is already sorted return; } int mid = left + (right - left) / 2; // Calculate midpoint to avoid overflow mergeSort(arr, left, mid); // Sort first half mergeSort(arr, mid + 1, right); // Sort second half merge(arr, left, mid, right); // Merge the sorted halves } int main() { // Step 1: Get array size from user int size; std::cout << "Enter the number of elements: "; std::cin >> size; if (size <= 0) { std::cout << "Number of elements must be positive." << std::endl; return 1; // Indicate an error } // Step 2: Get array elements from user std::vector<int> arr(size); std::cout << "Enter " << size << " integers:" << std::endl; for (int i = 0; i < size; ++i) { std::cout << "Element " << i + 1 << ": "; std::cin >> arr[i]; } // Step 3: Display the original array std::cout << "\nOriginal array: "; for (int x : arr) { std::cout << x << " "; } std::cout << std::endl; // Step 4: Perform Merge Sort mergeSort(arr, 0, size - 1); // Step 5: Display the sorted array std::cout << "Sorted array: "; for (int x : arr) { std::cout << x << " "; } std::cout << std::endl; return 0; }
Output
Clear
ADVERTISEMENTS