In place merging is still O(n) ?
c_cpp
18 days ago
2.4 kB
5
Indexable
Never
#include <iostream> #include <vector> void merge(std::vector<int>& arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; std::vector<int> L(n1); std::vector<int> R(n2); for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(std::vector<int>& arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } int main() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; int arr_size = arr.size(); mergeSort(arr, 0, arr_size - 1); for (int i = 0; i < arr_size; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; } // In place merging #include <iostream> #include <vector> void inPlaceMerge(std::vector<int>& arr, int l, int m, int r) { int i = l; // Current index in the first subarray int j = m + 1; // Current index in the second subarray while (i <= m && j <= r) { if (arr[i] <= arr[j]) { i++; } else { int value = arr[j]; int index = j; while (index > i) { arr[index] = arr[index - 1]; index--; } arr[i] = value; i++; m++; j++; } } } void mergeSort(std::vector<int>& arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); inPlaceMerge(arr, l, m, r); } } int main() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; int arr_size = arr.size(); mergeSort(arr, 0, arr_size - 1); for (int i = 0; i < arr_size; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }