c++ - Merge sort implementation -

i new c++ , trying develop code merge sort. tested sample array of size 5 answer put out code not right. can't figure what's going wrong. here code:

#include <iostream> #include <cstring> #include <sstream> #include <fstream> #include <iomanip> using namespace std; void merge(int, int, int, int*); void merge_sort(int low, int high, int* p){     int pivot;     static int i(1);     if (high>low)     {         cout << "calling merge_sort: "<<i<<endl; i++;         pivot = low + ((high - low)/2);         cout << pivot << endl;         merge_sort(low, pivot, p);         merge_sort(pivot+1, high, p);         merge(low, pivot, high, p);      } } void merge(int l, int pi, int h,int* arr) {             int start = l;         int mid = pi+1;         while((start<=pi)&&(mid <=h)){             if (arr[start] > arr[mid])             {                 int temp = arr[mid];                 arr[mid] = arr[start];                 arr[start] = temp;                 mid++;              }             else                 start++;     } } int main()  {     int a[] = {2, 42, 3, 7, 1};     merge_sort(0, 4, a);     (int = 0; i<=4 ; i++)         cout << a[i] << endl;     return (0);  } 

the output follows:

calling merge_sort: 1 2 calling merge_sort: 2 1 calling merge_sort: 3 0 calling merge_sort: 4 3 1 3 7 2 42 

i have seen codes merge sort implementation on stackoverflow use temporary array, want avoid.

any appreciated in sorting issue.

the logic in merge wrong. during merge phase know have 2 sections of sorted numbers. when compare , swap arr[start] , arr[mid] break sorting of top set of numbers if arr[start] > arr[mid+1]. example shows problem code 2 left in wrong place:

4 6 8 | 1 3 5  ->  1 6 8 | 4 3 5 ^       ^          ^         ^ 

in order keep 2 sections sorted have insert arr[start] in correct place in top set of numbers make complexity worse o(n lg n). reason second array used.

there method use smaller arrays original merging, these have overheads don't compromise complexity (or correctness). if want o(n lg n) in place sort quicksort or heapsort way go.