here is the code on how to mergesort a 2 equal sorted runs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <bits/stdc++.h>
using namespace std;
void SortTwoHalfSorted(int A[], int n)
{
int i = 0;
int j = n / 2;
// loop until end of array
while (j < n) {
// if two pointer is equal then go
// to next element of second half.
if (i == j)
j++;
// if element of first half is bigger
// than element of second half swap two
// elements and go next element of first half.
if (j < n && A[i] > A[j]) {
swap(A[i], A[j]);
}
i++;
}
}
// Driver code
int main()
{
int A[] = { 2, 3, 8, 1, 7, 10 };
int n = sizeof(A) / sizeof(A[0]);
SortTwoHalfSorted(A, n);
// Print sorted Array
for (int i = 0; i < n; i++)
cout << A[i] << " ";
return 0;
}
 
I am planning to do for multiple sorted runs that is not in the same size
this is how to find the sorted runs
for ( int i = 1; i < size; i++ )
{
if ( Array[i] < Array[i1] ) {
nruns++;
}
}
so my idea is to recursively mergesort every 2 sorted run until it becomes one sorted array. I've tried to code, but it didn't work
im think of using two variables to point I and j;
I will always start at 0 and j will start at start of next sorted run
so, if the data is 1,2,3,5,4,7,6,8,9,10
i is at 1
j is at 4
if i>j then insert j at i1
continue this step until last element of 2nd sorted run which from the data its 7
then the first two sorted runs is done
continue with the next two sorted from the array that has been sorted before
but at the same time i want the time complexity not more than O(N logN)