fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. //The merge function
  5. void merge(int a[], int startIndex, int endIndex)
  6. {
  7.  
  8. int size = (endIndex - startIndex) + 1;
  9. int *b = new int [size]();
  10.  
  11. int i = startIndex;
  12. int mid = (startIndex + endIndex)/2;
  13. int k = 0;
  14. int j = mid + 1;
  15.  
  16. while (k < size)
  17. {
  18. if((i<=mid) && (a[i] < a[j]))
  19. {
  20. b[k++] = a[i++];
  21. }
  22. else
  23. {
  24. b[k++] = a[j++];
  25. }
  26.  
  27. }
  28.  
  29. for(k=0; k < size; k++)
  30. {
  31. a[startIndex+k] = b[k];
  32. }
  33.  
  34. delete []b;
  35.  
  36. }
  37.  
  38. //The recursive merge sort function
  39. void merge_sort(int iArray[], int startIndex, int endIndex)
  40. {
  41. int midIndex;
  42.  
  43. //Check for base case
  44. if (startIndex >= endIndex)
  45. {
  46. return;
  47. }
  48.  
  49. //First, divide in half
  50. midIndex = (startIndex + endIndex)/2;
  51.  
  52. //First recursive call
  53. merge_sort(iArray, startIndex, midIndex);
  54.  
  55. //Second recursive call
  56. merge_sort(iArray, midIndex+1, endIndex);
  57.  
  58. //The merge function
  59. merge(iArray, startIndex, endIndex);
  60.  
  61. }
  62.  
  63. //The main function
  64. int main(int argc, char *argv[])
  65. {
  66. int iArray[10] = {2,5,6,4,7,2,8,3,9,10};
  67.  
  68. merge_sort(iArray, 0, 9);
  69.  
  70. //Print the sorted array
  71. for(int i=0; i < 10; i++)
  72. {
  73. cout << iArray[i] << endl;
  74. }
  75.  
  76. return 0;
  77. }
Success #stdin #stdout 0s 3460KB
stdin
Standard input is empty
stdout
2
2
3
4
5
6
7
8
9
10