TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
merge_sort.cpp
Go to the documentation of this file.
1
19#include <iostream>
20#include <vector>
21
37void merge(int *arr, int l, int m, int r) {
38 int n1 = m - l + 1;
39 int n2 = r - m;
40
41 std::vector<int> L(n1), R(n2);
42
43 for (int i = 0; i < n1; i++) L[i] = arr[l + i];
44 for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
45
46 int i = 0, j = 0, k = l;
47
48 while (i < n1 && j < n2) {
49 if (L[i] <= R[j]) {
50 arr[k] = L[i];
51 i++;
52 } else {
53 arr[k] = R[j];
54 j++;
55 }
56 k++;
57 }
58
59 while (i < n1) {
60 arr[k] = L[i];
61 i++;
62 k++;
63 }
64
65 while (j < n2) {
66 arr[k] = R[j];
67 j++;
68 k++;
69 }
70}
71
82void mergeSort(int *arr, int l, int r) {
83 if (l < r) {
84 int m = l + (r - l) / 2;
85 mergeSort(arr, l, m);
86 mergeSort(arr, m + 1, r);
87 merge(arr, l, m, r);
88 }
89}
90
95void show(int *arr, int size) {
96 for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
97 std::cout << "\n";
98}
99
101int main() {
102 int size;
103 std::cout << "Enter the number of elements: ";
104 std::cin >> size;
105
106 if (size <= 0) {
107 std::cout << "Invalid size.\n";
108 return 1;
109 }
110
111 int *arr = new int[size];
112 std::cout << "Enter the unsorted elements: ";
113 for (int i = 0; i < size; ++i) {
114 std::cin >> arr[i];
115 }
116
117 mergeSort(arr, 0, size - 1);
118 std::cout << "Sorted array: ";
119 show(arr, size);
120 delete[] arr;
121 return 0;
122}
123
void show(int *arr, int size)
void merge(int *arr, int l, int m, int r)
void mergeSort(int *arr, int l, int r)
int main()