write a very simple merge sort code in c++
- User
write a very simple merge sort code in c++
Assistant
Here's a very simple implementation of the Merge Sort algorithm in C++:
#include <iostream> #include <vector> using namespace std; // Function to 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 temporary 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 temporary 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 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 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); } } // Utility function to print an array void printArray(const vector<int>& arr) { for (int num : arr) { cout << num << " "; } cout << endl; } int main() { vector<int> arr = {12, 11, 13, 5, 6, 7}; cout << "Given array is: "; printArray(arr); mergeSort(arr, 0, arr.size() - 1); cout << "Sorted array is: "; printArray(arr); return 0; }This code:
- Implements the standard merge sort algorithm with a divide-and-conquer approach
- Uses a helper function
merge()to combine two sorted subarrays - Includes a simple
printArray()function to display the results - Demonstrates the sorting with a sample array in
main()
The algorithm works by:
- Recursively dividing the array into halves until each subarray has one element
- Then merging the subarrays back together 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.