fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. void mergeSort(int *array, int *temp, int leftStart, int rightEnd);
  6. void mergeHalves(int *array, int *temp, int leftStart, int rightEnd);
  7.  
  8. void printArray(int* array, int size,string message){
  9.     cout<<message<<endl;
  10.     for (int i = 0; i < size; i++)
  11.         cout << *(array+i) << "\t";
  12.     cout << endl;
  13. }
  14. int main(){
  15.     const int size = 10;
  16.     int myInts[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  17.     int temp[size] = {0};
  18.     printArray(myInts,size,"Input");
  19.     mergeSort(myInts, temp, 0, size-1);
  20.     printArray(myInts, size, "Output:");
  21.  
  22.     return 0;
  23. }
  24.  
  25. void mergeSort(int *array, int *temp, int leftStart, int rightEnd){
  26.     if (leftStart >= rightEnd)
  27.         return;
  28.  
  29.     int middle = (leftStart + rightEnd) / 2;
  30.  
  31.     mergeSort(array, temp, leftStart, middle);
  32.     mergeSort(array, temp, middle + 1, rightEnd);
  33.     mergeHalves(array,temp,leftStart,rightEnd);
  34.     return;
  35. }
  36.  
  37. void mergeHalves(int *array, int *temp, int leftStart, int rightEnd){
  38.     int middle = (rightEnd + leftStart) / 2;
  39.     int size = rightEnd - leftStart + 1;
  40.  
  41.     //cout << "Left: " << leftStart << ", Middle: " << middle << ", Right: " << rightEnd << endl;
  42.  
  43.     int left = leftStart;
  44.     int right = middle + 1;
  45.     int index = leftStart;
  46.  
  47.     while (left <= middle && right <= rightEnd){
  48.         if (array[left] <= array[right]){
  49.             temp[index] = array[left];
  50.             left++;
  51.         }else{
  52.             temp[index] = array[right];
  53.             right++;
  54.         }
  55.         index++;
  56.     }
  57.  
  58.  
  59.     memcpy(temp + index, array + left, (middle - left + 1) * sizeof(int));
  60.     memcpy(temp + index, array + right, (rightEnd - right + 1) * sizeof(int));
  61.     memcpy(array+leftStart, temp+leftStart, size * sizeof(int));
  62.  
  63. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input
9	8	7	6	5	4	3	2	1	0	
Output:
0	1	2	3	4	5	6	7	8	9
https://ideone.com/YNWhmE
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!