write a very simple merge sort code in c++
- User
write a very simple merge sort code in c++
Assistant
Simple Merge Sort in C++
Here's a basic implementation of the merge sort algorithm in C++:
#include <iostream> #include <vector> using namespace std; // Merge two sorted subarrays void merge(vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; // Create temporary arrays vector<int> L(n1), R(n2); // Copy data to temp arrays 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 temp arrays back into arr[left..right] int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Copy remaining elements of L[] if any while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy remaining elements of R[] if any while (j < n2) { arr[k] = R[j]; j++; k++; } } // Main merge sort function void mergeSort(vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // Sort first and second halves mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } } int main() { vector<int> arr = {12, 11, 13, 5, 6, 7}; cout << "Original array: "; for (int num : arr) { cout << num << " "; } cout << endl; mergeSort(arr, 0, arr.size() - 1); cout << "Sorted array: "; for (int num : arr) { cout << num << " "; } cout << endl; return 0; }Key Features:
- Uses recursion to divide the array into smaller subarrays
- Merges sorted subarrays back together
- Time complexity: O(n log n) in all cases
- Space complexity: O(n) due to temporary arrays
The code demonstrates the classic "divide and conquer" approach of merge sort, where the array is recursively divided into halves until single elements are reached, then merged back in sorted order.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.