Wir erhalten zwei sortierte Arrays. Wir müssen diese beiden Arrays so zusammenführen, dass die Anfangszahlen (nach vollständiger Sortierung) im ersten Array und die restlichen Zahlen im zweiten Array stehen. Zusätzlicher Platz in O(1) erlaubt.

Beispiel: 

Input: ar1[] = {10};
       ar2[] = {2, 3};
Output: ar1[] = {2}
        ar2[] = {3, 10}  

Input: ar1[] = {1, 5, 9, 10, 15, 20};
       ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
        ar2[] = {10, 13, 15, 20}

Diese Aufgabe ist einfach und O(m+n), wenn wir zusätzlichen Platz verwenden dürfen. Aber es wird wirklich kompliziert, wenn zusätzlicher Platz nicht erlaubt ist und nicht in weniger als O(m*n) Worst-Case-Zeit möglich erscheint. Obwohl weitere Optimierungen möglich sind
. Die Idee ist, beim letzten Element von ar2[] zu beginnen und es in ar1[] zu suchen. Wenn es ein größeres Element in ar1[] gibt, verschieben wir das letzte Element von ar1[] nach ar2[]. Um ar1[] und ar2[] sortiert zu halten, müssen wir das letzte Element von ar2[] an der richtigen Stelle in ar1[] platzieren. Wir können dafür den Typ  Insertion Sort verwenden.

1. Methode 1

Algorithmus: 

1) Iterate through every element of ar2[] starting from last 
   element. Do following for every element ar2[i]
    a) Store last element of ar1[i]: last = ar1[i]
    b) Loop from last element of ar1[] while element ar1[j] is 
       greater than ar2[i].
          ar1[j+1] = ar1[j] // Move element one position ahead
          j--
    c) If any element of ar1[] was moved or (j != m-1)
          ar1[j+1] = ar2[i] 
          ar2[i] = last

In der obigen Schleife werden Elemente in ar1[] und ar2[] immer sortiert gehalten.

Unten ist die Implementierung des obigen Algorithmus. 

// C++ program to merge two sorted
//  arrays with O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
 
// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements
    // of ar2[] starting from the last element
    for (int i = n - 1; i >= 0; i--)
    {
        /* Find the smallest element greater than ar2[i].
        Move all elements one position ahead till the
        smallest greater element is not found */
        int j, last = ar1[m - 1];
        for (j = m - 2; j >= 0
             && ar1[j] > ar2[i]; j--)
            ar1[j + 1] = ar1[j];
 
        // If there was a greater element
        if (j != m - 2 || last > ar2[i])
        {
            ar1[j + 1] = ar2[i];
            ar2[i] = last;
        }
    }
}
 
// Driver program
int main()
{
    int ar1[] = { 1, 5, 9, 10, 15, 20 };
    int ar2[] = { 2, 3, 8, 13 };
    int m = sizeof(ar1) / sizeof(ar1[0]);
    int n = sizeof(ar2) / sizeof(ar2[0]);
    merge(ar1, ar2, m, n);
 
    cout << "After Merging nFirst Array: ";
    for (int i = 0; i < m; i++)
        cout << ar1[i] << " ";
    cout << "nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << ar2[i] << " ";
    return 0;
}

// Java program program to merge two
// sorted arrays with O(1) extra space.
 
import java.util.Arrays;
 
class Test
{
    static int arr1[] = new int[]{1, 5, 9, 10, 15, 20};
    static int arr2[] = new int[]{2, 3, 8, 13};
     
    static void merge(int m, int n)
    {
        // Iterate through all elements of ar2[] starting from
        // the last element
        for (int i=n-1; i>=0; i--)
        {
            /* Find the smallest element greater than ar2[i]. Move all
               elements one position ahead till the smallest greater
               element is not found */
            int j, last = arr1[m-1];
            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)
                arr1[j+1] = arr1[j];
      
            // If there was a greater element
            if (j != m-2 || last > arr2[i])
            {
                arr1[j+1] = arr2[i];
                arr2[i] = last;
            }
        }
    }
     
    // Driver method to test the above function
    public static void main(String[] args)
    {
        merge(arr1.length,arr2.length);
        System.out.print("After Merging nFirst Array: ");
        System.out.println(Arrays.toString(arr1));
        System.out.print("Second Array:  ");
        System.out.println(Arrays.toString(arr2));
    }
}

# Python program to merge
# two sorted arrays
# with O(1) extra space.
 
# Merge ar1[] and ar2[]
# with O(1) extra space
def merge(ar1, ar2, m, n):
 
    # Iterate through all
    # elements of ar2[] starting from
    # the last element
    for i in range(n-1, -1, -1):
     
        # Find the smallest element
        # greater than ar2[i]. Move all
        # elements one position ahead
        # till the smallest greater
        # element is not found
        last = ar1[m-1]
        j=m-2
        while(j >= 0 and ar1[j] > ar2[i]):
            ar1[j+1] = ar1[j]
            j-=1
  
        # If there was a greater element
        if (j != m-2 or last > ar2[i]):
         
            ar1[j+1] = ar2[i]
            ar2[i] = last
  
# Driver program
 
ar1 = [1, 5, 9, 10, 15, 20]
ar2 = [2, 3, 8, 13]
m = len(ar1)
n = len(ar2)
 
merge(ar1, ar2, m, n)
  
print("After Merging \nFirst Array:", end="")
for i in range(m):
    print(ar1[i] , " ", end="")
 
print("\nSecond Array: ", end="")
for i in range(n):
    print(ar2[i] , " ", end="")
 
# This code is contributed
# by Anant Agarwal.

// C# program program to merge two
// sorted arrays with O(1) extra space.
using System;
 
// Java program program to merge two
// sorted arrays with O(1) extra space.
 
 
public class Test
{
    static int []arr1 = new int[]{1, 5, 9, 10, 15, 20};
    static int []arr2 = new int[]{2, 3, 8, 13};
     
    static void merge(int m, int n)
    {
        // Iterate through all elements of ar2[] starting from
        // the last element
        for (int i=n-1; i>=0; i--)
        {
            /* Find the smallest element greater than ar2[i]. Move all
            elements one position ahead till the smallest greater
            element is not found */
            int j, last = arr1[m-1];
            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)
                arr1[j+1] = arr1[j];
     
            // If there was a greater element
            if (j != m-2 || last > arr2[i])
            {
                arr1[j+1] = arr2[i];
                arr2[i] = last;
            }
        }
    }
     
    // Driver method to test the above function
    public static void Main()
    {
        merge(arr1.Length,arr2.Length);
        Console.Write("After Merging \nFirst Array: ");
        for(int i =0; i< arr1.Length;i++){
            Console.Write(arr1[i]+" ");
        }
        Console.Write("\nSecond Array: ");
        for(int i =0; i< arr2.Length;i++){
            Console.Write(arr2[i]+" ");
        }
    }
}
 
/*This code is contributed by 29AjayKumar*/

<?php
// PHP program to merge two sorted arrays with O(1) extra space.
  
// Merge ar1[] and ar2[] with O(1) extra space
function merge(&$ar1, &$ar2, $m, $n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for ($i = $n-1; $i >= 0; $i--)
    {
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        $last = $ar1[$m-1];
        for ($j = $m-2; $j >= 0 && $ar1[$j] > $ar2[$i]; $j--)
            $ar1[$j+1] = $ar1[$j];
  
        // If there was a greater element
        if ($j != $m-2 || $last > $ar2[$i])
        {
            $ar1[$j+1] = $ar2[$i];
            $ar2[$i] = $last;
        }
    }
}
  
// Driver program
 
$ar1 = array(1, 5, 9, 10, 15, 20);
$ar2 = array(2, 3, 8, 13);
$m = sizeof($ar1)/sizeof($ar1[0]);
$n = sizeof($ar2)/sizeof($ar2[0]);
merge($ar1, $ar2, $m, $n);
 
echo "After Merging \nFirst Array: ";
for ($i=0; $i<$m; $i++)
    echo $ar1[$i] . " ";
echo "\nSecond Array: ";
for ($i=0; $i<$n; $i++)
    echo $ar2[$i] ." ";
return 0;
?>

<script>
 
// Javascript program program to merge two
// sorted arrays with O(1) extra space.
 
    let arr1=[1, 5, 9, 10, 15, 20];
    let arr2=[2, 3, 8, 13];
     
    function merge(m,n)
    {
        // Iterate through all elements of ar2[] starting from
        // the last element
        for (let i=n-1; i>=0; i--)
        {
            /* Find the smallest element greater than ar2[i]. Move all
               elements one position ahead till the smallest greater
               element is not found */
            let j, last = arr1[m-1];
            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)
                arr1[j+1] = arr1[j];
       
            // If there was a greater element
            if (j != m-2 || last > arr2[i])
            {
                arr1[j+1] = arr2[i];
                arr2[i] = last;
            }
        }
    }
     
    // Driver method to test the above function
    merge(arr1.length,arr2.length);
    document.write("After Merging <br>First Array: ");
    for(let i=0;i<arr1.length;i++)
    {
        document.write(arr1[i]+" ");
    }
    document.write("<br>Second Array:  ");
    for(let i=0;i<arr2.length;i++)
    {
        document.write(arr2[i]+" ");
    }
     
     
    //  This code is contributed by avanitrachhadiya2155
     
</script>

Ausgabe: 

After Merging 
First Array: 1 2 3 5 8 9 
Second Array: 10 13 15 20

Zeitkomplexität: Die Zeitkomplexität des Codes/Algorithmus im ungünstigsten Fall beträgt O(m*n). Der schlimmste Fall tritt auf, wenn alle Elemente von ar1[] größer sind als alle Elemente von ar2[].

Illustration: 
 

<!— Anfängliche Arrays: 
ar1[] = {1, 5, 9, 10, 15, 20}; 
ar2[] = {2, 3, 8, 13 };
Nach der ersten Iteration: 
ar1[] = {1, 5, 9, 10, 13, 15}; 
ar2[] = {2, 3, 8 , 20}; 
// 20 wird von ar1[] nach ar2[] verschoben 
// 13 von ar2[] wird in ar1[] eingefügt
Nach der zweiten Iteration: 
ar1[] = {1, 5, 8, 9, 10, 13}; 
ar2[] = {2, 3 , 15, 20}; 
// 15 wird von ar1[] nach ar2[] verschoben 
// 8 von ar2[] wird in ar1[] eingefügt
Nach der dritten Iteration: 
ar1[] = {1, 3, 5, 8, 9, 10}; 
ar2[] = { 2 , 13, 15, 20}; 
// 13 wird von ar1[] nach ar2[] verschoben 
// 3 von ar2[] wird in ar1[] eingefügt
Nach der vierten Iteration: 
ar1[] = {1, 2, 3, 5, 8, 9}; 
ar2[] = {10, 13, 15, 20}; 
// 10 wird von ar1[] nach ar2[] verschoben 
// 2 von ar2[] wird in ar1[] eingefügt 
—!>

Methode 2:

Die Lösung kann weiter optimiert werden, indem beobachtet wird, dass beim parallelen Durchlaufen der beiden sortierten Arrays, wenn wir feststellen, dass das j-te zweite Array-Element kleiner als das i-te erste Array-Element ist, das j-te Element eingeschlossen werden muss und ein k-tes Element im ersten Array ersetzt. Diese Beobachtung hilft uns beim folgenden Algorithmus

Algorithmus

1) Initialize i,j,k as 0,0,n-1 where n is size of arr1 
2) Iterate through every element of arr1 and arr2 using two pointers i and j respectively
    if arr1[i] is less than arr2[j]
        increment i
    else
        swap the arr2[j] and arr1[k]
        increment j and decrement k

3) Sort both arr1 and arr2 

Unten ist die Implementierung des obigen Algorithmus

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge two arrays
void merge(int arr1[], int arr2[], int n, int m)
{
    int i = 0, j = 0, k = n - 1;
   
    // Untill i less than equal to k
    // or j is less tha m
    while (i <= k && j < m) {
        if (arr1[i] < arr2[j])
            i++;
        else {
            swap(arr2[j++], arr1[k--]);
        }
    }
   
    // Sort first array
    sort(arr1, arr1 + n);
   
    // Sort second array
    sort(arr2, arr2 + m);
}
 
// Driver Code
int main()
{
 
    int ar1[] = { 1, 5, 9, 10, 15, 20 };
    int ar2[] = { 2, 3, 8, 13 };
    int m = sizeof(ar1) / sizeof(ar1[0]);
    int n = sizeof(ar2) / sizeof(ar2[0]);
    merge(ar1, ar2, m, n);
 
    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < m; i++)
        cout << ar1[i] << " ";
    cout << "\nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << ar2[i] << " ";
    return 0;
}

// Java program for the above approach
import java.util.Arrays;
import java.util.Collections;
 
class GFG {
    static int arr1[] = new int[] { 1, 5, 9, 10, 15, 20 };
    static int arr2[] = new int[] { 2, 3, 8, 13 };
 
    // Function to merge two arrays
    static void merge(int m, int n)
    {
        int i = 0, j = 0, k = n - 1;
        while (i <= k && j < m) {
            if (arr1[i] < arr2[j])
                i++;
            else {
                int temp = arr2[j];
                arr2[j] = arr1[k];
                arr1[k] = temp;
                j++;
                k--;
            }
        }
        Arrays.sort(arr1);
        Arrays.sort(arr2);
    }
 
    public static void main(String[] args)
    {
        merge(arr1.length, arr2.length);
        System.out.print("After Merging \nFirst Array: ");
        System.out.println(Arrays.toString(arr1));
        System.out.print("Second Array:  ");
        System.out.println(Arrays.toString(arr2));
    }
}

Nach dem Zusammenführen
Erste Reihe: 1 2 3 5 8 9
Zweite Reihe: 10 13 15 20

Komplexitäten:

Zeitkomplexität: Die Zeitkomplexität beim Durchlaufen der Arrays in der While-Schleife beträgt im schlimmsten Fall O(n+m) und die Sortierung ist O(nlog(n) + mlog(m)). Die Gesamtzeitkomplexität des Codes wird also O((n+m)log(n+m)).

Raumkomplexität: Da die Funktion für keine Operationen ein zusätzliches Array verwendet, beträgt die Raumkomplexität O (1).

Methode 3:

Algorithmus:

1) Initialize i with 0
2) Iterate while loop untill last element of array 1 is greater than first element of array 2
          if arr1[i] greater than first element of arr2
              swap arr1[i] with arr2[0]
              sort arr2
          incrementing i 

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
 
void merge(int arr1[], int arr2[], int n, int m) {
        int i=0;
        // while loop till last element of array 1(sorted) is greater than
          // first element of array 2(sorted)
        while(arr1[n-1]>arr2[0])
        {
            if(arr1[i]>arr2[0])
            {
                // swap arr1[i] with first element
                  // of arr2 and sorting the updated
                // arr2(arr1 is already sorted)
                swap(arr1[i],arr2[0]);
                sort(arr2,arr2+m);
            }
            i++;
        }
    }
 
int main()
{
 
    int ar1[] = { 1, 5, 9, 10, 15, 20 };
    int ar2[] = { 2, 3, 8, 13 };
    int m = sizeof(ar1) / sizeof(ar1[0]);
    int n = sizeof(ar2) / sizeof(ar2[0]);
    merge(ar1, ar2, m, n);
 
    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < m; i++)
        cout << ar1[i] << " ";
    cout << "\nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << ar2[i] << " ";
    return 0;
 
}

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
 
class GFG{
 
static int arr1[] = new int[]{ 1, 5, 9, 10, 15, 20 };
static int arr2[] = new int[]{ 2, 3, 8, 13 };
 
static void merge(int n, int m)
{
    int i = 0;
    int temp = 0;
     
    // While loop till last element
    // of array 1(sorted)
    // is greater than first element
    // of array 2(sorted)
    while (arr1[n - 1] > arr2[0])
    {
        if (arr1[i] > arr2[0])
        {
             
            // Swap arr1[i] with first element
            // of arr2 and sorting the updated
            // arr2(arr1 is already sorted)
            // swap(arr1[i],arr2[0]);
            temp = arr1[i];
            arr1[i] = arr2[0];
            arr2[0] = temp;
            Arrays.sort(arr2);
        }
        i++;
    }
}
 
// Driver code
public static void main(String[] args)
{
    merge(arr1.length, arr2.length);
 
    System.out.print("After Merging \nFirst Array: ");
    System.out.println(Arrays.toString(arr1));
     
    System.out.print("Second Array:  ");
    System.out.println(Arrays.toString(arr2));
}
}
 
// This code is contributed by Aakash Tiwari(nighteagle)

Nach dem Zusammenführen
Erste Reihe: 1 2 3 5 8 9
Zweite Reihe: 10 13 15 20

Effizientes Zusammenführen von zwei sortierten Arrays mit O(1) zusätzlichem Speicherplatz
 

Methode 4: Lassen Sie die Länge des kürzeren Arrays 'm' und das größere Array 'n' sein

Schritt 1 : Wählen Sie das kürzere Array aus und finden Sie den Index, an dem die Partition erstellt werden soll. Ähnlich wie hier https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

             Schritt 1 : Partitionieren Sie das kürzere Array an seinem Median (l1) .

             Schritt 2 : Wählen Sie die ersten n-l1 Elemente aus dem zweiten Array aus.

             Schritt 3 : Vergleichen Sie die Randelemente, dh

                            wenn l1 < r2 und l2 < r2 ist, haben wir den Index gefunden

                           andernfalls, wenn l1 > r2 , müssen wir im linken Subarray suchen

                           Andernfalls müssen wir im richtigen Subarray suchen

HINWEIS: Dieser Schritt speichert alle kleinsten Elemente im kürzeren Array.

Schritt 2 : Vertausche alle Elemente bis zum Index (i) des kürzeren Arrays mit den ersten ni Elementen des größeren Arrays.

Schritt 3 : Sortieren Sie beide Arrays.

::::: Wenn len(arr1) > len(arr2) werden alle kleinsten Elemente in arr2 gespeichert, also müssen wir alle Elemente in arr1 verschieben , da wir zuerst arr1 drucken müssen .

             Schritt 4 : Drehen Sie das größere Array (arr1) m -mal gegen den Uhrzeigersinn.

             Schritt 5 : Vertausche die ersten m Elemente beider Arrays.

#include <bits/stdc++.h>
using namespace std;
 
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void rotate(int a[], int n, int idx)
{
    int i;
    for (i = 0; i < idx / 2; i++)
        swap(a[i], a[idx - 1 - i]);
    for (i = idx; i < (n + idx) / 2; i++)
        swap(a[i], a[n - 1 - (i - idx)]);
    for (i = 0; i < n / 2; i++)
        swap(a[i], a[n - 1 - i]);
}
 
void sol(int a1[], int a2[], int n, int m)
{
    int l = 0, h = n - 1, idx = 0;
    //---------------------------------------------------------
    while (l <= h) {
        // select the median of the remaining subarray
        int c1 = (l + h) / 2;
        // select the first elements from the larger array
        // equal to the size of remaining portion to the
        // right of the smaller array
        int c2 = n - c1 - 1;
        int l1 = a1[c1];
        int l2 = a2[c2 - 1];
        int r1 = c1 == n - 1 ? INT_MAX : a1[c1 + 1];
        int r2 = c2 == m ? INT_MAX : a2[c2];
        // compare the border elements and check for the
        // target index
        if (l1 > r2) {
            h = c1 - 1;
            if (h == -1)
                idx = 0;
        }
        else if (l2 > r1) {
            l = c1 + 1;
            if (l == n - 1)
                idx = n;
        }
        else {
            idx = c1 + 1;
            break;
        }
    }
 
    for (int i = idx; i < n; i++)
        swap(a1[i], a2[i - idx]);
 
    sort(a1, a1 + n);
 
    sort(a2, a2 + m);
}
 
void merge(int arr1[], int arr2[], int n, int m)
{
    // code here
    if (n > m) {
        sol(arr2, arr1, m, n);
        rotate(arr1, n, n - m);
 
        for (int i = 0; i < m; i++)
            swap(arr2[i], arr1[i]);
    }
    else {
        sol(arr1, arr2, n, m);
    }
}
 
int main()
{
 
    int ar1[] = { 1, 5, 9, 10, 15, 20 };
    int ar2[] = { 2, 3, 8, 13 };
    int m = sizeof(ar1) / sizeof(ar1[0]);
    int n = sizeof(ar2) / sizeof(ar2[0]);
    merge(ar1, ar2, m, n);
 
    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < m; i++)
        cout << ar1[i] << " ";
    cout << "\nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << ar2[i] << " ";
    return 0;
}

# Python program to merge
# two sorted arrays
# with O(1) extra space.
 
# Merge ar1[] and ar2[]
# with O(1) extra space
 
 
def rotate(a, n, idx):
    for i in range((int)(idx/2)):
        a[i], a[idx-1-i] = a[idx-1-i], a[i]
    for i in range(idx, (int)((n+idx)/2)):
        a[i], a[n-1-(i-idx)] = a[n-1-(i-idx)], a[i]
    for i in range((int)(n/2)):
        a[i], a[n-1-i] = a[n-1-i], a[i]
 
 
def sol(a1, a2, n, m):
    l = 0
    h = n-1
    idx = 0
    while (l <= h):
        c1 = (int)((l+h)/2)
        c2 = n-c1-1
        l1 = a1[c1]
        l2 = a2[c2-1]
        r1 = sys.maxint if c1 == n-1 else a1[c1+1]
        r2 = sys.maxint if c2 == m else a2[c2]
        if l1 > r2:
            h = c1-1
            if h == -1:
                idx = 0
        elif l2 > r1:
            l = c1+1
            if l == n-1:
                idx = n
        else:
            idx = c1+1
            break
    for i in range(idx, n):
        a1[i], a2[i-idx] = a2[i-idx], a1[i]
 
    a1.sort()
    a2.sort()
 
 
def merge(a1, a2, n, m):
    if n > m:
        sol(a2, a1, m, n)
        rotate(a1, n, n-m)
        for i in range(m):
            a1[i], a2[i] = a2[i], a1[i]
    else:
        sol(a1, a2, n, m)
# Driver program
 
 
ar1 = [1, 5, 9, 10, 15, 20]
ar2 = [2, 3, 8, 13]
m = len(ar1)
n = len(ar2)
 
merge(ar1, ar2, m, n)
 
print("After Merging \nFirst Array:", end="")
for i in range(m):
    print(ar1[i], " ", end="")
print("\nSecond Array: ", end="")
for i in range(n):
    print(ar2[i], " ", end="")
# This code is contributed
# by Aditya Anand.

Nach dem Zusammenführen
Erste Reihe: 1 2 3 5 8 9
Zweite Reihe: 10 13 15 20

Zeitkomplexität: O(min(nlogn, mlogm))
 

Methode 5 [Einfügungssortierung mit gleichzeitiger Zusammenführung]

Sich nähern:

1. Sortieren Sie Liste 1, indem Sie immer mit Kopf/Erster von Liste 2 vergleichen und ggf. tauschen . 2. Führen
Sie nach jedem Kopf/Erster-Tausch das Einfügen des vertauschten Elements an der richtigen Position in Liste 2 durch, wodurch Liste 2 schließlich am Ende sortiert wird. 

Führen Sie für jedes ausgetauschte Element aus Liste 1 eine Einfügungssortierung in Liste 2 durch, um die richtige Position zu finden, sodass beim Sortieren von Liste 1 auch Liste 2 sortiert wird.

#include <bits/stdc++.h>
using namespace std;
 
void merge(int arr1[], int arr2[], int n, int m)
{
    // two pointer to iterate
    int i = 0;
    int j = 0;
    while (i < n && j < m) {
        // if arr1[i] <= arr2[j] then both array is already
        // sorted
        if (arr1[i] <= arr2[j]) {
            i++;
        }
        else if (arr1[i] > arr2[j]) {
            // if arr1[i]>arr2[j] then first we swap both
            // element so that arr1[i] become smaller means
            // arr1[] become sorted then we check that
            // arr2[j] is smaller then all other element in
            // right side of arr2[j] if arr2[] is not sorted
            // then we linearly do sorting
            // means while adjecent element are less than
            // new arr2[j] we do sorting like by chnaging
            // position of element by shifting one position
            // toward left
            swap(arr1[i], arr2[j]);
            i++;
            if (j < m - 1 && arr2[j + 1] < arr2[j]) {
                int temp = arr2[j];
                int tempj = j + 1;
                while (arr2[tempj] < temp && tempj < m) {
                    arr2[tempj - 1] = arr2[tempj];
                    tempj++;
                }
                arr2[tempj - 1] = temp;
            }
        }
    }
}
 
int main()
{
 
    int ar1[] = { 1, 5, 9, 10, 15, 20 };
    int ar2[] = { 2, 3, 8, 13 };
    int m = sizeof(ar1) / sizeof(ar1[0]);
    int n = sizeof(ar2) / sizeof(ar2[0]);
    merge(ar1, ar2, m, n);
 
    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < m; i++)
        cout << ar1[i] << " ";
    cout << "\nSecond Array: ";
    for (int i = 0; i < n; i++)
        cout << ar2[i] << " ";
    return 0;
}

# code contributed by mahee96
 
# "Insertion sort of list 2 with swaps from list 1"
#
# swap elements to get list 1 correctly, meanwhile
# place the swapped item in correct position of list 2
# eventually list 2 is also sorted
# Time = O(m*n) or O(n*m)
# AUX = O(1)
def merge(arr1, arr2):
    x = arr1; y = arr2
    end = len(arr1)
    i = 0
    while(i < end):                 # O(m) or O(n)
        if(x[i] > y[0]):
            swap(x,y,i,0)
            insert(y,0)             # O(n) or O(m) number of shifts
        i+=1
 
# O(n):
def insert(y, i):
    orig = y[i]
    i+=1
    while (i<len(y) and y[i]<orig):
        y[i-1] = y[i]
        i+=1
    y[i-1] = orig
 
def swap(x,y,i,j):
    temp = x[i]
    x[i] = y[j]
    y[j] = temp
 
def test():
    c1 = [2, 3, 8, 13]
    c2 = [1, 5, 9, 10, 15, 20 ]
    for _ in range(2):
        merge(c1,c2)
        print(c1,c2)
        c1, c2 = c2, c1
 
test()

Nach dem Zusammenführen
Erste Reihe: 1 2 3 5 8 9
Zweite Reihe: 10 13 15 20

Zeitkomplexität: O(m*n) Liste 1 Traversierung und Liste 2 Einfügungen
Hilfsraum: O(1)
Wenn m == n: Zeit = O(n^2) Einfügungssortierkomplexität

Verwandte Artikel: 
Zwei sortierte Arrays  
zusammenführen k sortierte Arrays zusammenführen | Satz 1
Danke an Shubham Chauhan für den Vorschlag der ersten Lösung und Himanshu Kaushik für die zweite Lösung. Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten
 

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .