SHARE
TWEET

mergesort

a guest Feb 28th, 2020 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3.  
  4. using namespace std;
  5.  
  6. void merge(long* arr, int l, int m, int r) {
  7.     // Create new arrays for left and right partitions
  8.     int lSize = m - l;
  9.     int rSize = r - m;
  10.     long* lPart = new long[lSize];
  11.     long* rPart = new long[rSize];
  12.  
  13.     // Copy elements into their respective partitions.
  14.     for (int i = 0; i < lSize; i++) {
  15.         lPart[i] = arr[i + l];
  16.     }
  17.  
  18.     for (int i = 0; i < rSize; i++) {
  19.         rPart[i] = arr[i + m];  
  20.     }
  21.  
  22.     // Add elements from new partitions back into new array, sorted
  23.     //     until one of the arrays reaches the end.
  24.     int lIdx = 0;
  25.     int rIdx = 0;
  26.     int arrIdx = l;
  27.  
  28.     while (lIdx < lSize && rIdx < rSize) {
  29.         if (lPart[lIdx] <= rPart[rIdx]) {
  30.             arr[arrIdx] = lPart[lIdx];
  31.             lIdx++;
  32.         } else if (rPart[rIdx] <= lPart[lIdx]) {
  33.             arr[arrIdx] = rPart[rIdx];
  34.             rIdx++;
  35.         }
  36.         arrIdx++;
  37.     }
  38.  
  39.     // Finish off the remaining elements in the right and left arrays
  40.     while (lIdx < lSize) {
  41.         arr[arrIdx++] = lPart[lIdx++];
  42.     }
  43.  
  44.     while (rIdx < rSize) {
  45.         arr[arrIdx++] = rPart[rIdx++];
  46.     }
  47. }
  48.  
  49. void mergeSort(long* arr, int size) {
  50.     for (int partitionSize = 1; partitionSize < size; partitionSize *= 2) {
  51.  
  52.         for (int left = 0; left < size - 1; left += partitionSize * 2) {
  53.  
  54.             int mid = min(left + partitionSize, size);
  55.             int right = min(left + partitionSize * 2, size);
  56.             merge(arr, left, mid, right);
  57.         }
  58.     }  
  59. }
  60.  
  61.  
  62. int main() {
  63.     long arr[] = {8, 2, 3, 7, 6, 5, 4, 2, 7};
  64.     mergeSort(arr, 9);
  65.     for (int i = 0; i < 9; i++) {
  66.         cout << arr[i] << " ";
  67.     }
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top