Araf_12

Merge Sort

May 29th, 2023 (edited)
16
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. // Merge sort in C++
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. // Merge two subarrays L and M into arr
  7. void merge(int arr[], int p, int q, int r) {
  8.  
  9.   // Create L ← A[p..q] and M ← A[q+1..r]
  10.   int n1 = q - p + 1;
  11.   int n2 = r - q;
  12.  
  13.   int L[n1], M[n2];
  14.  
  15.   for (int i = 0; i < n1; i++)
  16.     L[i] = arr[p + i];
  17.   for (int j = 0; j < n2; j++)
  18.     M[j] = arr[q + 1 + j];
  19.  
  20.   // Maintain current index of sub-arrays and main array
  21.   int i, j, k;
  22.   i = 0;
  23.   j = 0;
  24.   k = p;
  25.  
  26.   // Until we reach either end of either L or M, pick larger among
  27.   // elements L and M and place them in the correct position at A[p..r]
  28.   while (i < n1 && j < n2) {
  29.     if (L[i] <= M[j]) {
  30.       arr[k] = L[i];
  31.       i++;
  32.     } else {
  33.       arr[k] = M[j];
  34.       j++;
  35.     }
  36.     k++;
  37.   }
  38.  
  39.   // When we run out of elements in either L or M,
  40.   // pick up the remaining elements and put in A[p..r]
  41.   while (i < n1) {
  42.     arr[k] = L[i];
  43.     i++;
  44.     k++;
  45.   }
  46.  
  47.   while (j < n2) {
  48.     arr[k] = M[j];
  49.     j++;
  50.     k++;
  51.   }
  52. }
  53.  
  54. // Divide the array into two subarrays, sort them and merge them
  55. void mergeSort(int arr[], int l, int r) {
  56.   if (l < r) {
  57.     // m is the point where the array is divided into two subarrays
  58.     int m = l + (r - l) / 2;
  59.  
  60.     mergeSort(arr, l, m);
  61.     mergeSort(arr, m + 1, r);
  62.  
  63.     // Merge the sorted subarrays
  64.     merge(arr, l, m, r);
  65.   }
  66. }
  67.  
  68. // Print the array
  69. void printArray(int arr[], int size) {
  70.   for (int i = 0; i < size; i++)
  71.     cout << arr[i] << " ";
  72.   cout << endl;
  73. }
  74.  
  75. // Driver program
  76. int main() {
  77.   int arr[] = {6, 5, 12, 10, 9, 1};
  78.   int size = sizeof(arr) / sizeof(arr[0]);
  79.  
  80.   mergeSort(arr, 0, size - 1);
  81.  
  82.   cout << "Sorted array: \n";
  83.   printArray(arr, size);
  84.   return 0;
  85. }
Add Comment
Please, Sign In to add comment