92 lines
2.1 KiB
C++
Executable File
92 lines
2.1 KiB
C++
Executable File
#include <iostream>
|
|
using namespace std;
|
|
|
|
void merge(int array[], int left, int mid, int right) {
|
|
int leftArrLen = mid - left + 1;
|
|
int rightArrLen = right - mid;
|
|
|
|
// Create temp arrays
|
|
int leftArray[leftArrLen];
|
|
int rightArray[rightArrLen];
|
|
|
|
// Copy data to temp arrays leftArray[] and rightArray[]
|
|
for (int i = 0; i < leftArrLen; i++) {
|
|
leftArray[i] = array[left + i];
|
|
}
|
|
|
|
for (auto i = 0; i < rightArrLen; i++) {
|
|
rightArray[i] = array[mid + 1 + i];
|
|
}
|
|
|
|
int leftArrIndex = 0; // Initial index of first sub-array
|
|
int rightArrIndex = 0; // Initial index of second sub-array
|
|
int mergedArrIndex = left; // Initial index of merged array
|
|
|
|
// Merge the temp arrays back into array[left..right]
|
|
while (leftArrIndex < leftArrLen && rightArrIndex < rightArrLen) {
|
|
// Choose one of the two elements at current positions of left and right arrays
|
|
if (leftArray[leftArrIndex] <= rightArray[rightArrIndex]) {
|
|
array[mergedArrIndex] = leftArray[leftArrIndex];
|
|
leftArrIndex++;
|
|
} else {
|
|
array[mergedArrIndex] = rightArray[rightArrIndex];
|
|
rightArrIndex++;
|
|
}
|
|
mergedArrIndex++;
|
|
}
|
|
|
|
// Copy the remaining elements of
|
|
// left[], if there are any
|
|
while (leftArrIndex < leftArrLen) {
|
|
array[mergedArrIndex] = leftArray[leftArrIndex];
|
|
leftArrIndex++;
|
|
mergedArrIndex++;
|
|
}
|
|
|
|
// Copy the remaining elements of
|
|
// right[], if there are any
|
|
while (rightArrIndex < rightArrLen) {
|
|
array[mergedArrIndex] = rightArray[rightArrIndex];
|
|
rightArrIndex++;
|
|
mergedArrIndex++;
|
|
}
|
|
}
|
|
|
|
|
|
void mergeSort(int arr[], int left, int right) {
|
|
if (left >= right) {
|
|
return;
|
|
}
|
|
|
|
int middle = (left + right) / 2;
|
|
mergeSort(arr, left, middle);
|
|
mergeSort(arr, middle + 1, right);
|
|
merge(arr, left, middle, right);
|
|
}
|
|
|
|
// 4 1 3 5 2
|
|
// 4 1 3 5 2 [4, 1] [3]
|
|
// 4 1 3 5 2 [^1, 4] [^3]
|
|
// 1 1 3 5 2 [1, ^4] [^3]
|
|
// 1 3 3 5 2 [1, ^4] [3]^
|
|
// 1 3 4 5 2 [^5] [^2]
|
|
// 1 3 4 2 2 [^5] [2]^
|
|
// 1 3 4 2 5
|
|
|
|
|
|
|
|
int main() {
|
|
int N = 50;
|
|
int arr[N];
|
|
for (int i = 0; i < N; i++) {
|
|
arr[i] = N - i;
|
|
}
|
|
|
|
mergeSort(arr, 0, N - 1);
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
cout << arr[i] << " ";
|
|
}
|
|
cout << endl;
|
|
return 0;
|
|
} |