TLE in merge two sorted array without extra space

Question

1.00/5 (2 votes)

See more:

Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.

Input: 
n = 4, arr1[] = [1 3 5 7] 
m = 5, arr2[] = [0 2 6 8 9]
Output: 
arr1[] = [0 1 2 3]
arr2[] = [5 6 7 8 9]

What I have tried:

C++

void merge(long long arr1[], long long arr2[], int n, int m) 
{ 
   for(int i=0;i<n;i++) {
      if(arr1[i] > arr2[0]) {
         swap(arr1[i],arr2[0]);
      }

      sort(arr2,arr2+m);
   }
}

Posted 26-Mar-22 2:17am

Animesh _1SG20IS008

Updated 27-Mar-22 11:57am

merano99

v5

Add a Solution

Comments

Richard MacCutchan 26-Mar-22 9:53am

Do you have a question?

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2022-03-27T11:57:00

Quote:
TLE in merge two sorted array without extra space

In your case, "without extra space" is matching a special kind of algorithm named "in place".
See this article: In-Place Merge Sort - GeeksforGeeks[^].
The "In-Place Merge Sort" algorithm contain the "merge" operation you are looking for.
Usually, it operate on a large array containing 2 sorted sub-arrays, in your case it is 2 separate arrays, you have to use a trick to simulate a large single array.
Take that arr of size m+n is arr1 if index below m, and arr2 otherwise with a position (index-m).
Common technique for in place merge: The rotation

x x x x           arr1
        x x x x x arr2
1 3 5 7 0 2 6 8 9
0 1 3 5 7 2 6 8 9
0 1 2 3 5 7 6 8 9
0 1 2 3 5 6 7 8 9

Only need 1 extra place.

merano99 · Answer 2 · 2022-03-26T14:39:00

To merge two sorted arrays in sorted order without using any extra space
you already realised a loop for one array. You need a secod one for the
second array.

You've already noticed that a feature to swap items would be useful.
However, the suggested call

C++

swap(arr1[i],arr2[0]);

cannot work like this.

Even if both arrays were sorted at the beginning, one of the arrays could no longer be sorted after the action. That still needs to be resolved.

merano99 · Answer 3 · 2022-03-26T22:39:00

Instead of just swapping the elements, it would be more efficient to sort them directly. If an element from
arr1 is larger than one from arr2, one can assume that arr2[0] should be inserted into arr1, since it is the
smallest there.To paste the element from arr1 to arr2, you need to find a suitable place in arr2 before copying.
I propose the following declaration for the function :

C++

// arrx position in arr1, arr2 is start of array, m is size of arr2
void replace(int* arrx, int arr2[], int m);

TLE in merge two sorted array without extra space

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0