Programa Python3 para fusionar 3 arrays ordenadas

Dadas 3 arrays (A, B, C) que están ordenadas en orden ascendente, debemos fusionarlas en orden ascendente y generar la array D. 

Ejemplos: 

Input : A = [1, 2, 3, 4, 5] 
        B = [2, 3, 4]
        C = [4, 5, 6, 7]
Output : D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]

Input : A = [1, 2, 3, 5]
        B = [6, 7, 8, 9 ]
        C = [10, 11, 12]
Output: D = [1, 2, 3, 5, 6, 7, 8, 9. 10, 11, 12]

Método 1 (dos arreglos a la vez) 
Hemos discutido en Combinar 2 arreglos ordenados . Entonces, primero podemos fusionar dos arrays y luego fusionar la resultante con la tercera array. Complejidad de tiempo para fusionar dos arrays O (m + n). Entonces, para fusionar la tercera array, la complejidad del tiempo se convertirá en O (m + n + o). Tenga en cuenta que esta es de hecho la mejor complejidad de tiempo que se puede lograr para este problema. 
Complejidad espacial : dado que fusionamos dos arrays a la vez, necesitamos otra array para almacenar el resultado de la primera fusión. Esto eleva la complejidad del espacio a O(m+n). Tenga en cuenta que el espacio requerido para contener el resultado de 3 arrays se ignora al calcular la complejidad. 

Algoritmo 

function merge(A, B)
    Let m and n be the sizes of A and B
    Let D be the array to store result
   
    // Merge by taking smaller element from A and B
    while i < m and j < n
        if A[i] <= B[j]
            Add A[i] to D and increment i by 1
        else Add B[j] to D and increment j by 1

    // If array A has exhausted, put elements from B
    while j < n
        Add B[j] to D and increment j by 1
   
    // If array B has exhausted, put elements from A
    while i < n
        Add A[j] to D and increment i by 1
   
    Return D

function merge_three(A, B, C)
    T = merge(A, B)
    return merge(T, C)

Las implementaciones se dan a continuación.

# Python program to merge three sorted arrays
# by merging two at a time.
 
def merge_two(a, b):
    (m, n) = (len(a), len(b))
    i = j = 0
 
    # Destination Array
    d = []
 
    # Merge from a and b together
    while i < m and j < n:
        if a[i] <= b[j]:
            d.append(a[i])
            i += 1
        else:
            d.append(b[j])
            j += 1
 
    # Merge from a if b has run out
    while i < m:
        d.append(a[i])
        i += 1
 
    # Merge from b if a has run out
    while j < n:
        d.append(b[j])
        j += 1
 
    return d
 
def merge(a, b, c):
    t = merge_two(a, b)
    return merge_two(t, c)
 
if __name__ == "__main__":
    A = [1, 2, 3, 5]
    B = [6, 7, 8, 9]
    C = [10, 11, 12]
    print(merge(A, B, C))

[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]

Método 2 (Tres arreglos a la vez) 
La complejidad espacial del método 1 se puede mejorar fusionando los tres arreglos. 
 

function merge-three(A, B, C)
    Let m, n, o be size of A, B, and C
    Let D be the array to store the result
    
    // Merge three arrays at the same time
    while i < m and j < n and k < o
        Get minimum of A[i], B[j], C[i]
        if the minimum is from A, add it to 
           D and advance i
        else if the minimum is from B add it 
                to D and advance j
        else if the minimum is from C add it 
                to D and advance k
    
   // After above step at least 1 array has 
   // exhausted. Only C has exhausted
   while i < m and j < n
       put minimum of A[i] and B[j] into D
       Advance i if minimum is from A else advance j 
   
   // Only B has exhausted
   while i < m and k < o
       Put minimum of A[i] and C[k] into D
       Advance i if minimum is from A else advance k
 
   // Only A has exhausted
   while j < n and k < o
       Put minimum of B[j] and C[k] into D
       Advance j if minimum is from B else advance k

   // After above steps at least 2 arrays have 
   // exhausted
   if A and B have exhausted take elements from C
   if B and C have exhausted take elements from A
   if A and C have exhausted take elements from B
   
   return D

Complejidad: La complejidad del tiempo es O(m+n+o) ya que procesamos cada elemento de las tres arrays una vez. Solo necesitamos una array para almacenar el resultado de la fusión y, por lo tanto, ignorando esta array, la complejidad del espacio es O (1).

 La implementación del algoritmo se da a continuación:

# Python program to merge three sorted arrays
# simultaneously.
 
def merge_three(a, b, c):
    (m, n, o) = (len(a), len(b), len(c))
    i = j = k = 0
 
    # Destination array
    d = []
 
    while i < m and j < n and k < o:
 
        # Get Minimum element
        m = min(a[i], b[j], c[k])
 
        # Add m to D
        d.append(m)
 
        # Increment the source pointer which
        # gives m
        if a[i] == m:
            i += 1
        elif b[j] == m:
            j += 1
        elif c[k] == m:
            k += 1
 
    # Merge a and b in c has exhausted
    while i < m and j < n:
        if a[i] <= b[k]:
            d.append(a[i])
            i += 1
        else:
            d.append(b[j])
            j += 1
 
    # Merge b and c if a has exhausted
    while j < n and k < o:
        if b[j] <= c[k]:
            d.append(b[j])
            j += 1
        else:
            d.append(c[k])
            k += 1
 
    # Merge a and c if b has exhausted
    while i < m and k < o:
        if a[i] <= c[k]:
            d.append(a[i])
            i += 1
        else:
            d.append(c[k])
            k += 1
 
    # Take elements from a if b and c
    # have exhausted
    while i < m:
        d.append(a[i])
        i += 1
 
    # Take elements from b if a and c
    # have exhausted
    while j < n:
        d.append(b[j])
        j += 1
 
    # Take elements from c if a and
    # b have exhausted
    while k < o:
        d.append(c[k])
        k += 1
 
    return d
 
if __name__ == "__main__":
    a = [1, 2, 41, 52, 84]
    b = [1, 2, 41, 52, 67]
    c = [1, 2, 41, 52, 67, 85]
 
    print(merge_three(a, b, c))

[1, 1, 1, 2, 2, 41, 41, 52, 52, 67, 67, 85]

Nota: si bien es relativamente fácil implementar procedimientos directos para fusionar dos o tres arrays, el proceso se vuelve engorroso si queremos fusionar 4 o más arrays. En tales casos, debemos seguir el procedimiento que se muestra en Merge K Sorted Arrays .

Otro enfoque (sin preocuparse por la array agotadora):
el código escrito anteriormente se puede acortar con el código siguiente. Aquí no necesitamos escribir código si alguna array se agota.

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

# Python program to merge three sorted arrays
# Without caring about the exhausting array
 
# import the module
import sys
 
# A[], B[], C[]: input arrays
# Function to merge three sorted lists into a single
# list.
 
 
def merge3sorted(A, B, C):
    ans = []
    l1 = len(A)
    l2 = len(B)
    l3 = len(C)
    i, j, k = 0, 0, 0
    while(i < l1 or j < l2 or k < l3):
        # Assigning a, b, c with max values so that if
        # any value is not present then also we can sort
        # the array.
        a = sys.maxsize
        b = sys.maxsize
        c = sys.maxsize
 
        # a, b, c variables are assigned only if the
        # value exist in the array.
        if(i < l1):
            a = A[i]
        if(j < l2):
            b = B[j]
        if(k < l3):
            c = C[k]
 
        #  Checking if 'a' is the minimum
        if(a <= b and a <= c):
            ans.append(a)
            i = i+1
 
        #  Checking if 'b' is the minimum
        if(b <= a and b <= c):
            ans.append(b)
            j = j+1
 
        #  Checking if 'c' is the minimum
        if(c <= a and c <= b):
            ans.append(c)
            k = k+1
    return ans
 
 
def printeSorted(List):
    for x in List:
        print(x, end=" ")
 
 
# Driver program to test above functions
A = [1, 2, 41, 52, 84]
B = [1, 2, 41, 52, 67]
C = [1, 2, 41, 52, 67, 85]
 
final_ans = merge3sorted(A, B, C)
printeSorted(final_ans)
 
# This code is contributed by Pushpesh Raj

 Complejidad de tiempo: O(m+n+o) donde m, n, o son las longitudes de las arrays 1, 2 y 3.

Consulte el artículo completo sobre Merge 3 Sorted Arrays para obtener más detalles.