Combinar K arrays ordenadas de diferentes tamaños | (Enfoque divide y vencerás)

Dadas k arrays ordenadas de diferente longitud, combínelas en una sola array de modo que la array combinada también esté ordenada.
Ejemplos: 
 

Input : {{3, 13}, 
        {8, 10, 11}
        {9, 15}}
Output : {3, 8, 9, 10, 11, 13, 15}

Input : {{1, 5}, 
         {2, 3, 4}}
Output : {1, 2, 3, 4, 5}

Sea S el número total de elementos en todos los arreglos.
Enfoque simple : un enfoque simple es agregar las arrays una tras otra y ordenarlas. La complejidad del tiempo en este caso será O( S * log(S)) .
Enfoque eficiente : una solución eficiente será tomar pares de arrays en cada paso. Luego fusione los pares utilizando la técnica de dos punteros de fusionar dos arrays ordenadas . Por lo tanto, después de fusionar todos los pares, el número de arrays se reducirá a la mitad. 
Continuaremos esto hasta que el número de arreglos restantes no llegue a 1. Por lo tanto, el número de pasos requeridos será del orden log(k) y dado que en cada paso, estamos tomando el tiempo O(S) para realizar el fusionar operaciones, la complejidad de tiempo total de este enfoque se vuelveO(S * log(k)) .
Ya hemos discutido este enfoque para fusionar K arrays ordenadas de los mismos tamaños .
Dado que en este problema las arrays son de diferentes tamaños, utilizaremos arrays dinámicas (p. ej., vector en el caso de C++ o arraylist en el caso de Java) porque reducen significativamente el número de líneas y la carga de trabajo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to merge K sorted arrays of
// different arrays
 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to merge two arrays
vector<int> mergeTwoArrays(vector<int> l, vector<int> r)
{
    // array to store the result
    // after merging l and r
    vector<int> ret;
 
    // variables to store the current
    // pointers for l and r
    int l_in = 0, r_in = 0;
 
    // loop to merge l and r using two pointer
    while (l_in + r_in < l.size() + r.size()) {
        if (l_in != l.size() && (r_in == r.size() || l[l_in] < r[r_in])) {
            ret.push_back(l[l_in]);
            l_in++;
        }
        else {
            ret.push_back(r[r_in]);
            r_in++;
        }
    }
 
    return ret;
}
 
// Function to merge all the arrays
vector<int> mergeArrays(vector<vector<int> > arr)
{
    // 2D-array to store the results of
    // a step temporarily
    vector<vector<int> > arr_s;
 
    // Loop to make pairs of arrays and merge them
    while (arr.size() != 1) {
 
        // To clear the data of previous steps
        arr_s.clear();
 
        for (int i = 0; i < arr.size(); i += 2) {
            if (i == arr.size() - 1)
                arr_s.push_back(arr[i]);
 
            else
                arr_s.push_back(mergeTwoArrays(arr[i],
                                               arr[i + 1]));
        }
 
        arr = arr_s;
    }
 
    // Returning the required output array
    return arr[0];
}
 
// Driver Code
int main()
{
    // Input arrays
    vector<vector<int> > arr{ { 3, 13 },
                              { 8, 10, 11 },
                              { 9, 15 } };
    // Merged sorted array
    vector<int> output = mergeArrays(arr);
 
    for (int i = 0; i < output.size(); i++)
        cout << output[i] << " ";
 
    return 0;
}

# Python3 program to merge K sorted
# arrays of different arrays
 
# Function to merge two arrays
def mergeTwoArrays(l, r):
 
    # array to store the result
    # after merging l and r
    ret = []
 
    # variables to store the current
    # pointers for l and r
    l_in, r_in = 0, 0
 
    # loop to merge l and r using two pointer
    while l_in + r_in < len(l) + len(r):
        if (l_in != len(l) and
           (r_in == len(r) or
            l[l_in] < r[r_in])):
                 
            ret.append(l[l_in])
            l_in += 1
         
        else:
            ret.append(r[r_in])
            r_in += 1
 
    return ret
 
# Function to merge all the arrays
def mergeArrays(arr):
 
    # 2D-array to store the results
    # of a step temporarily
    arr_s = []
 
    # Loop to make pairs of arrays
    # and merge them
    while len(arr) != 1:
 
        # To clear the data of previous steps
        arr_s[:] = []
 
        for i in range(0, len(arr), 2):
            if i == len(arr) - 1:
                arr_s.append(arr[i])
 
            else:
                arr_s.append(mergeTwoArrays(arr[i],
                                            arr[i + 1]))
 
        arr = arr_s[:]
 
    # Returning the required output array
    return arr[0]
 
# Driver Code
if __name__ == "__main__":
 
    # Input arrays
    arr = [[3, 13],
        [8, 10, 11],
        [9, 15]]
             
    # Merged sorted array
    output = mergeArrays(arr)
 
    for i in range(0, len(output)):
        print(output[i], end = " ")
 
# This code is contributed by Rituraj Jain

<script>
 
// Javascript program to merge K sorted arrays of
// different arrays
 
// Function to merge two arrays
function mergeTwoArrays(l, r)
{
 
    // array to store the result
    // after merging l and r
    var ret = [];
 
    // variables to store the current
    // pointers for l and r
    var l_in = 0, r_in = 0;
 
    // loop to merge l and r using two pointer
    while (l_in + r_in < l.length + r.length) {
        if (l_in != l.length && (r_in == r.length || l[l_in] < r[r_in])) {
            ret.push(l[l_in]);
            l_in++;
        }
        else {
            ret.push(r[r_in]);
            r_in++;
        }
    }
 
    return ret;
}
 
// Function to merge all the arrays
function mergeArrays(arr)
{
    // 2D-array to store the results of
    // a step temporarily
    var arr_s = [];
 
    // Loop to make pairs of arrays and merge them
    while (arr.length != 1) {
 
        // To clear the data of previous steps
        arr_s = [];
 
        for (var i = 0; i < arr.length; i += 2) {
            if (i == arr.length - 1)
                arr_s.push(arr[i]);
 
            else
                arr_s.push(mergeTwoArrays(arr[i],
                                               arr[i + 1]));
        }
 
        arr = arr_s;
    }
 
    // Returning the required output array
    return arr[0];
}
 
// Driver Code
// Input arrays
var arr = [ [ 3, 13 ],
                          [ 8, 10, 11 ],
                          [ 9, 15 ] ];
// Merged sorted array
var output = mergeArrays(arr);
for (var i = 0; i < output.length; i++)
    document.write(output[i] + " ");
 
// This code is contributed by rrrtnx.
</script>

3 8 9 10 11 13 15

Complejidad de tiempo: O(S*logK)
Espacio auxiliar: O(logK)
Tenga en cuenta que existe una mejor solución usando heap (o cola de prioridad) . La complejidad temporal de la solución basada en almacenamiento dinámico es O(N Log k) donde N es el número total de elementos en todos los K arreglos.