Fusión eficiente de dos arrays ordenadas con O (1) espacio adicional y O (NlogN + MlogM)

Dadas dos arrays ordenadas, arr1[] y arr2[] , la tarea es fusionarlas en tiempo O(Nlog(N) + Mlog(M)) con O(1) espacio adicional en una array ordenada donde N es el tamaño de la primera array arr1[] y M es el tamaño de la segunda array arr2[] .

Ejemplos:  

Entrada: arr1[] = {1, 5, 9, 10, 15, 20}, arr2[] = {2, 3, 8, 13} 
Salida: 1 2 3 5 8 9 10 13 15 20

Entrada: arr1[] = {4, 9, 15, 20}, arr2[] = {2, 6, 7, 13} 
Salida: 2 4 6 7 9 13 15 20  

Enfoque: Ya se ha discutido un enfoque en este artículo. En este artículo, se discutirá un enfoque aún más eficiente.  

• Forme dos arrays bitónicas comparando el elemento más alto de una array con el elemento más bajo de la segunda array, de modo que ambas arrays contengan solo aquellos elementos que estarán allí después de la clasificación de ambas arrays.
• Ahora, ordene ambas arrays por separado.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
 
#include <iostream>
using namespace std;
 
// Reducing the gap by a factor of 2
int nextGap(int gap)
{
    if (gap <= 1)
        return 0;
    return (gap / 2) + (gap % 2);
}
 
// Function to merge two sorted
// arrays with O(1) extra space
int mergeTwoSortedArray(int* arr1,
                        int* arr2,
                        int n, int m)
{
    int x = min(n, m);
 
    // Form both arrays to be bitonic
    for (int i = 0; i < x; i++) {
        if (arr1[n - i - 1] > arr2[i])
            swap(arr1[n - i - 1], arr2[i]);
    }
 
    // Now both the arrays contain the numbers
    // which should be there in the result
    // Sort the array individually by inplace algo
    for (int gap = nextGap(n); gap > 0;
         gap = nextGap(gap)) {
 
        // Comparing elements in the first array
        for (int i = 0; i + gap < n; i++)
            if (arr1[i] > arr1[i + gap])
                swap(arr1[i], arr1[i + gap]);
    }
 
    // Sort the second array
    for (int gap = nextGap(m); gap > 0;
         gap = nextGap(gap)) {
 
        // Comparing elements in the second array
        for (int i = 0; i + gap < m; i++)
            if (arr2[i] > arr2[i + gap])
                swap(arr2[i], arr2[i + gap]);
    }
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";
    for (int j = 0; j < m; j++)
        cout << arr2[j] << " ";
}
 
// Driver code
int main()
{
    int arr1[] = { 1, 5, 9, 10, 15, 20 };
    int n = sizeof(arr1) / sizeof(int);
    int arr2[] = { 2, 3, 8, 13 };
    int m = sizeof(arr2) / sizeof(int);
 
    mergeTwoSortedArray(arr1, arr2, n, m);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Reducing the gap by a factor of 2
    static int nextGap(int gap)
    {
        if (gap <= 1)
            return 0;
        return (int)((gap / 2) + (gap % 2));
    }
     
    // Function to merge two sorted
    // arrays with O(1) extra space
    static void mergeTwoSortedArray(int []arr1,
                                    int []arr2,
                                    int n, int m)
    {
        int x = Math.min(n, m);
     
        // Form both arrays to be bitonic
        for (int i = 0; i < x; i++)
        {
            if (arr1[n - i - 1] > arr2[i])
            {
                // swap(arr1[n - i - 1], arr2[i]);
                int temp = arr1[n - i - 1];
                arr1[n - i - 1] = arr2[i];
                arr2[i] = temp;
            }
        }
     
        // Now both the arrays contain the numbers
        // which should be there in the result
        // Sort the array individually by inplace algo
        for (int gap = nextGap(n); gap > 0;
            gap = nextGap(gap))
        {
     
            // Comparing elements in the first array
            for (int i = 0; i + gap < n; i++)
                if (arr1[i] > arr1[i + gap])
                {
                    // swap(arr1[i], arr1[i + gap]);
                    int temp = arr1[i];
                    arr1[i] = arr1[i + gap];
                    arr1[i + gap] = temp;
                }
        }
     
        // Sort the second array
        for (int gap = nextGap(m); gap > 0;
            gap = nextGap(gap))
        {
     
            // Comparing elements in the second array
            for (int i = 0; i + gap < m; i++)
                if (arr2[i] > arr2[i + gap])
                {
                    // swap(arr2[i], arr2[i + gap]);
                    int temp = arr2[i];
                    arr2[i] = arr2[i + gap];
                    arr2[i + gap] = temp;
                }
        }
        for (int i = 0; i < n; i++)
            System.out.print(arr1[i] + " ");
        for (int j = 0; j < m; j++)
            System.out.print(arr2[j] + " ");
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr1[] = { 1, 5, 9, 10, 15, 20 };
        int n = arr1.length;
        int arr2[] = { 2, 3, 8, 13 };
        int m = arr2.length;
     
        mergeTwoSortedArray(arr1, arr2, n, m);
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Reducing the gap by a factor of 2
def nextGap(gap) :
    if (gap <= 1) :
        return 0;
    res = (gap // 2) + (gap % 2);
    return res;
 
# Function to merge two sorted
# arrays with O(1) extra space
def mergeTwoSortedArray(arr1, arr2, n, m) :
 
    x = min(n, m);
 
    # Form both arrays to be bitonic
    for i in range(x) :
        if (arr1[n - i - 1] > arr2[i]) :
            arr1[n - i - 1],arr2[i] = arr2[i], arr1[n- i - 1];
 
    # Now both the arrays contain the numbers
    # which should be there in the result
    # Sort the array individually by inplace algo
    gap = nextGap(n);
    while gap > 0 :
         
        # Comparing elements in the first array
        i = 0;
         
        while i + gap < n :
             
            if (arr1[i] > arr1[i + gap]) :
                arr1[i], arr1[i + gap] = arr1[i + gap],arr1[i];
                 
            i += 1;
             
        gap = nextGap(gap)
 
    # Sort the second array
    gap = nextGap(m);
     
    while gap > 0 :
         
        # Comparing elements in the second array
        i = 0
        while i + gap < m :
            if (arr2[i] > arr2[i + gap]) :
                arr2[i], arr2[i + gap] = arr2[i + gap], arr2[i];
                 
            i += 1;
             
        gap = nextGap(gap)
             
    for i in range(n) :
        print(arr1[i], end = " ");
         
    for j in range(m) :
        print(arr2[j], end = " ");
 
# Driver code
if __name__ == "__main__" :
 
    arr1 = [ 1, 5, 9, 10, 15, 20 ];
    n = len(arr1);
    arr2 = [ 2, 3, 8, 13 ];
    m = len(arr2);
 
    mergeTwoSortedArray(arr1, arr2, n, m);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Reducing the gap by a factor of 2
    static int nextGap(int gap)
    {
        if (gap <= 1)
            return 0;
        return (int)((gap / 2) + (gap % 2));
    }
     
    // Function to merge two sorted
    // arrays with O(1) extra space
    static void mergeTwoSortedArray(int []arr1,
                                    int []arr2,
                                    int n, int m)
    {
        int x = Math.Min(n, m);
     
        // Form both arrays to be bitonic
        for (int i = 0; i < x; i++)
        {
            if (arr1[n - i - 1] > arr2[i])
            {
                int temp = arr1[n - i - 1];
                arr1[n - i - 1] = arr2[i];
                arr2[i] = temp;
            }
        }
     
        // Now both the arrays contain the numbers
        // which should be there in the result
        // Sort the array individually by inplace algo
        for (int gap = nextGap(n); gap > 0;
            gap = nextGap(gap))
        {
     
            // Comparing elements in the first array
            for (int i = 0; i + gap < n; i++)
                if (arr1[i] > arr1[i + gap])
                {
                    int temp = arr1[i];
                    arr1[i] = arr1[i + gap];
                    arr1[i + gap] = temp;
                }
        }
     
        // Sort the second array
        for (int gap = nextGap(m); gap > 0;
            gap = nextGap(gap))
        {
     
            // Comparing elements in the second array
            for (int i = 0; i + gap < m; i++)
                if (arr2[i] > arr2[i + gap])
                {
                    int temp = arr2[i];
                    arr2[i] = arr2[i + gap];
                    arr2[i + gap] = temp;
                }
        }
        for (int i = 0; i < n; i++)
            Console.Write(arr1[i] + " ");
        for (int j = 0; j < m; j++)
            Console.Write(arr2[j] + " ");
    }
     
    // Driver code
    public static void Main()
    {
        int []arr1 = { 1, 5, 9, 10, 15, 20 };
        int n = arr1.Length;
        int []arr2 = { 2, 3, 8, 13 };
        int m = arr2.Length;
     
        mergeTwoSortedArray(arr1, arr2, n, m);
    }
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript implementation of the approach
     
    // Reducing the gap by a factor of 2
    function nextGap(gap)
    {
        if (gap <= 1)
            return 0;
        return (parseInt(gap / 2, 10) + (gap % 2));
    }
       
    // Function to merge two sorted
    // arrays with O(1) extra space
    function mergeTwoSortedArray(arr1, arr2, n, m)
    {
        let x = Math.min(n, m);
       
        // Form both arrays to be bitonic
        for (let i = 0; i < x; i++)
        {
            if (arr1[n - i - 1] > arr2[i])
            {
                let temp = arr1[n - i - 1];
                arr1[n - i - 1] = arr2[i];
                arr2[i] = temp;
            }
        }
       
        // Now both the arrays contain the numbers
        // which should be there in the result
        // Sort the array individually by inplace algo
        for (let gap = nextGap(n); gap > 0;
            gap = nextGap(gap))
        {
       
            // Comparing elements in the first array
            for (let i = 0; i + gap < n; i++)
                if (arr1[i] > arr1[i + gap])
                {
                    let temp = arr1[i];
                    arr1[i] = arr1[i + gap];
                    arr1[i + gap] = temp;
                }
        }
       
        // Sort the second array
        for (let gap = nextGap(m); gap > 0;
            gap = nextGap(gap))
        {
       
            // Comparing elements in the second array
            for (let i = 0; i + gap < m; i++)
                if (arr2[i] > arr2[i + gap])
                {
                    let temp = arr2[i];
                    arr2[i] = arr2[i + gap];
                    arr2[i + gap] = temp;
                }
        }
        for (let i = 0; i < n; i++)
            document.write(arr1[i] + " ");
        for (let j = 0; j < m; j++)
            document.write(arr2[j] + " ");
    }
     
    let arr1 = [ 1, 5, 9, 10, 15, 20 ];
    let n = arr1.length;
    let arr2 = [ 2, 3, 8, 13 ];
    let m = arr2.length;
 
    mergeTwoSortedArray(arr1, arr2, n, m);
         
</script>

1 2 3 5 8 9 10 13 15 20

Complejidad de tiempo: O(Nlog(N) + Mlog(M))