.

[lindsayy]

here is the code on how to mergesort a 2 equal sorted runs

  #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[i-1] ) {
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 i-1
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)

[jonnin]

you may want a merge function. This works on 2 sorted lists to produce a third sorted list.
that is, roughly:

int index{0},left{0}, right{0}; //a and b, one and two, however you want to think of 2 containers. 
for(the size of left + size of right containers (not sizeof, but count of items) )
{
if(container1[left] < container2[right])
{
newcontainer[index++]  = container1[left++];
}
else 
newcontainer[index++]  = container2[right++];
if left is equal to container1 size or right is equal to container2 size, break. 
}
now copy the rest of whichever container is not empty into the list. 

this takes 2 sorted lists and makes 1 out of them. You can rewrite the idea to use recursion, which is not necessary, or make a variety of tweak to it, but that is the idea. An example of a do-over would be 2 vectors, sorted in reverse order, pop back the one you put in the new list, and go until both are empty.
for large items, it can be worthwhile to just make the combined list a container of pointers back to the originals, depending on what you need done and how much space you have and how fast it runs and all kinds of things.

it is possible to do it all at once, to sort and combine. I am not sure it is more efficient to do that, as now the sort has to deal with more items, which slows it down a little, does it slow it down more than a O(N) pass through the 'merge'? Not sure, but assuming the 2 sorts can run in parallel as threads... probably using merge is better?! All you have to do here is append one list into the other before sorting; trying to do 2 into a third all split up is also doable but its a lot of extra gibberish code for no tangible gains...

[lindsayy]

thank you @jonnin..but im not familiar with container..how can i use it?..do i need to include any library?..and yeah..i wan planning to do so tweak on mergesort

[jonnin]

container is a generic term for {array, string, list, vector, ...} type things. Here, it probably means 'array' to you.
its a 'type' that can 'contain' more than one of 'another type'.
a string contains a number of characters, for example.
a vector is an array-like thing built into c++ <vector> header ... it can also function as a 'stack' with 'push' and 'pop' like functions built into it. These work best off the 'back' (the highest array index) so if sorted backwards, popping the back is really 'iterating it like you would a sorted array from low to high'. Its ok if you have no idea what I just said. It was just an example of alternate ways to implement 'merge'.

if you want to write mergesort to juggle 3 arrays at once, that will be a good exercise, but it is certainly the hard way to solve the problem.

[lindsayy]

i see, i think i understan it already, but how to use your code in line 10-12? i mean how to write in c++

[jonnin]

if you have a for loop:
int i{}; //important that it is here
for(i = 0; i < something; i++)
{
    ...merge stuff...
     if(left == container1.size || right == container2.size)
      break; //the loop stops now.  
}
if(left != container1.size) //you did not use all of container 1. 
while(left < container1.size)
   newarray[index++] = container1[left++];
else// do container 2 instead, same thing
while(right < container2.size) 
  newarray[index++] = container2[right++];

be careful not to be off by one etc in these, but it should work if you take care with it.
verify it.. merge a couple of sorted arrays and see if it works

if you are using arrays, you just know their size
eg int x[100] size is 100
the .size would be 100 in that case.

so the idea is that you have 2 sorted lists:
1 2 3
1 1 9 9 9
------------------
it looks at both, takes the 1 off the first one (arbitrary when equal)
23
11999
->1
now it looks at 1 and 2, and picks the smaller, 1
23
1999
-> 1 1
then it does that again, 1 and 2
23
999
-> 1 1 1
and now 2 and 9, then 3 and 9, ...
empty
999
-> 1 1 1 2 3
but now the top list is empty: left == size of that list.
stop, and loop, copying the rest of list 2 into the target:
1 1 1 2 3 9 9 9

[lindsayy]

Thabk you so much jonnin

[keskiverto]

Why did you erase the title text of the thread? Don't.