Программа Javascript для объединения 3 отсортированных массивов

Даны 3 массива (A, B, C), отсортированные в порядке возрастания, нам необходимо объединить их вместе в порядке возрастания и вывести массив D.

Примеры:

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]

Способ 1 (два массива одновременно)
Мы обсуждали слияние двух отсортированных массивов. Таким образом, мы можем сначала объединить два массива, а затем объединить полученный результат с третьим массивом. Временная сложность объединения двух массивов O(m+n). Таким образом, для объединения третьего массива временная сложность станет O (m + n + o). Обратите внимание, что это действительно лучшая временная сложность, которую можно достичь для этой задачи.
Сложность пространства : поскольку мы объединяем два массива одновременно, нам нужен еще один массив для хранения результата первого слияния. Это повышает сложность пространства до O (m + n). Обратите внимание, что пространство, необходимое для хранения результата 3 массивов, игнорируется при вычислении сложности.

Алгоритм

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)

Реализации приведены ниже

Выход:

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

Способ 2 (три массива одновременно)
Пространственная сложность метода 1 может быть улучшена путем объединения трех массивов вместе.

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

Сложность: временная сложность равна O(m+n+o), так как мы обрабатываем каждый элемент из трех массивов один раз. Нам нужен только один массив для хранения результата слияния, поэтому, игнорируя этот массив, сложность пространства составляет O (1).

Реализация алгоритма приведена ниже:

Примечание. Хотя реализовать прямые процедуры для слияния двух или трех массивов относительно легко, процесс становится громоздким, если мы хотим объединить 4 или более массивов. В таких случаях мы должны следовать процедуре, показанной в Merge K Sorted Arrays.
Другой подход (не заботясь об исчерпывающем массиве):
Код, написанный выше, может быть сокращен приведенным ниже кодом. Здесь нам не нужно писать код, если какой-либо массив исчерпается.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(m+n+o), где m, n, o — длины 1-го, 2-го и 3-го массивов.

Пожалуйста, обратитесь к полной статье о слиянии 3 отсортированных массивов для получения более подробной информации!