Posted on by Kalkicode
Code Array

# Merge elements of three sorted arrays

In this article, we will explore the problem of merging three sorted arrays into a single sorted array. We'll discuss the problem statement, provide a step-by-step explanation of the algorithm to solve it, and analyze the time complexity of the provided code example. By the end of this article, you'll have a clear understanding of how to merge three sorted arrays efficiently.

## Problem Statement

Given three sorted arrays, we need to merge them into a single sorted array. For example, consider the three arrays:

• `a`: `[-2, 5, 7, 7, 10]`
• `b`: `[-4, 0, 1, 2, 3]`
• `c`: `[-1, -1, 2, 4, 5, 9]`

The merged and sorted array would be: `[-4, -2, -1, -1, 0, 1, 2, 2, 3, 4, 5, 5, 7, 7, 9, 10]`

## Solution Idea

To merge three sorted arrays efficiently, we can follow a merging algorithm similar to the merge step in the merge sort algorithm. We'll maintain three pointers to keep track of our progress in each array. At each step, we compare the elements pointed to by these pointers and choose the smallest element to insert into the merged array. We then move the pointer of the array from which we selected the element.

## Standard Pseudocode

Here is the pseudocode that outlines the approach to merge three sorted arrays:

``````function merge3SortedArray(a, b, c):
Initialize pointers p1, p2, p3 to 0

Initialize an empty array result

while any of p1, p2, p3 is less than the length of respective arrays:
Compare a[p1], b[p2], c[p3]
Choose the smallest element among them

Add the smallest element to the result array

Move the pointer of the array from which the element was chosen

return result``````

## Algorithm Explanation

1. We start by initializing three pointers `p1`, `p2`, and `p3` to 0, which will keep track of our progress in arrays `a`, `b`, and `c` respectively.

2. We initialize an empty array called `result` that will store the merged and sorted elements.

3. We enter a loop that continues until any of the pointers `p1`, `p2`, or `p3` reaches the end of their respective arrays.

4. In each iteration of the loop, we compare the elements `a[p1]`, `b[p2]`, and `c[p3]` to find the smallest among them.

5. We choose the smallest element and add it to the `result` array.

6. We then move the pointer of the array from which the smallest element was chosen.

7. The loop continues until we have exhausted any of the arrays.

8. After the loop completes, we return the `result` array, which now contains the merged and sorted elements.

## Code Solution

``````// C Program
// Merge elements of three sorted arrays
#include <stdio.h>

void merge3SortedArray(int a[], int b[], int c[],
int result[], int l1, int l2, int l3)
{
int i = 0;
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = b[p2];
p2++;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1++;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2++;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3++;
}
i++;
}
}
// Display array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
int main()
{
// Sorted Arrays
int a[] = {
-2 , 5 , 7 , 7 , 10
};
int b[] = {
-4 , 0 , 1 , 2 , 3
};
int c[] = {
-1 , -1 , 2 , 4 , 5 , 9
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
int n = l1 + l2 + l3;
// Collecting resultant element
int result[n];
// Merge
merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
printArr(result, n);
return 0;
}``````

#### Output

``  -4  -2  -1  -1  0  1  2  2  3  4  5  5  7  7  9  10``
``````/*
Java Program
Merge elements of three sorted arrays
In sorted order
*/

public class Sorting
{
public void merge3SortedArray(
int[] a, int[] b, int[] c, int[] result,
int l1, int l2, int l3)
{
// Auxiliary variables
int i = 0;
int p1 = 0;
int p2 = 0;
int p3 = 0;

// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = b[p2];
p2++;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1++;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2++;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3++;
}
i++;
}
}
// Display array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args)
{
// Sorted Arrays
int[] a =  {
-2 , 5 , 7 , 7 , 10
};
int[] b =  {
-4 , 0 , 1 , 2 , 3
};
int[] c =  {
-1 , -1 , 2 , 4 , 5 , 9
};
// Get the size
int l1 = a.length;
int l2 = b.length;
int l3 = c.length;
int n = l1 + l2 + l3;
// Collecting resultant element
int[] result = new int[n];
// Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements

}
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting
{
public: void merge3SortedArray(
int a[], int b[], int c[], int result[],
int l1, int l2, int l3)
{
// Auxiliary variables
int i = 0;
int p1 = 0;
int p2 = 0;
int p3 = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = b[p2];
p2++;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1++;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2++;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3++;
}
i++;
}
}
// Display array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
};
int main()
{
// Sorted Arrays
int a[] = {
-2 , 5 , 7 , 7 , 10
};
int b[] = {
-4 , 0 , 1 , 2 , 3
};
int c[] = {
-1 , -1 , 2 , 4 , 5 , 9
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
int n = l1 + l2 + l3;
// Collecting resultant element
int result[n];
// Merge
task->merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
return 0;
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````// Include namespace system
using System;
/*
Csharp Program
Merge elements of three sorted arrays
In sorted order
*/
public class Sorting
{
public void merge3SortedArray(
int[] a, int[] b, int[] c, int[] result,
int l1, int l2, int l3)
{
// Auxiliary variables
int i = 0;
int p1 = 0;
int p2 = 0;
int p3 = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = b[p2];
p2++;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1++;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2++;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3++;
}
i++;
}
}
// Display array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
// Sorted Arrays
int[] a = {
-2 , 5 , 7 , 7 , 10
};
int[] b = {
-4 , 0 , 1 , 2 , 3
};
int[] c = {
-1 , -1 , 2 , 4 , 5 , 9
};
// Get the size
int l1 = a.Length;
int l2 = b.Length;
int l3 = c.Length;
int n = l1 + l2 + l3;
// Collecting resultant element
int[] result = new int[n];
// Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
}
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````package main
import "fmt"
/*
Go Program
Merge elements of three sorted arrays
In sorted order
*/

func merge3SortedArray(a[] int, b[] int, c[] int,
result[] int, l1 int, l2 int, l3 int) {
// Auxiliary variables
var i int = 0
var p1 int = 0
var p2 int = 0
var p3 int = 0
// This loop are combining sorted elements
for (i < l1 + l2 + l3) {
if p1 < l1 && p2 < l2 && p3 < l3 {
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if a[p1] < b[p2] {
if a[p1] < c[p3] {
// Find smallest element in first array
result[i] = a[p1]
p1++
} else {
// Find smallest element in third array
result[i] = c[p3]
p3++
}
} else if b[p2] < c[p3] {
// Find smallest element in second array
result[i] = b[p2]
p2++
} else {
// Find smallest element in third array
result[i] = c[p3]
p3++
}
} else if p1 < l1 {
// When element exists in first array
if p2 < l2 {
// When element also exists in second array
if a[p1] < b[p2] {
result[i] = a[p1]
p1++
} else {
result[i] = b[p2]
p2++
}
} else if p3 < l3 {
//  When element also exists in third array
if a[p1] < c[p3] {
result[i] = a[p1]
p1++
} else {
result[i] = c[p3]
p3++
}
} else {
// When element exists in only first array
result[i] = a[p1]
p1++
}
} else if p2 < l2 {
// When element exists in second array
if p3 < l3 {
// When element exists in third array
if b[p2] < c[p3] {
result[i] = b[p2]
p2++
} else {
result[i] = c[p3]
p3++
}
} else {
// When element exists in only second array
result[i] = c[p2]
p2++
}
} else {
// When element exists in third array
result[i] = c[p3]
p3++
}
i++
}
}
// Display array elements
func printArr(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func main() {

// Sorted Arrays
var a = [] int { -2, 5, 7, 7, 10 }
var b = [] int { -4, 0, 1, 2, 3}
var c = [] int { -1, -1, 2, 4, 5, 9}
// Get the size
var l1 int = len(a)
var l2 int = len(b)
var l3 int = len(c)
var n int = l1 + l2 + l3
// Collecting resultant element
var result = make([] int, n)
// Merge
merge3SortedArray(a, b, c, result, l1, l2, l3)
// Display array elements
printArr(result, n)
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````<?php
/*
Php Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting
{
public	function merge3SortedArray(\$a, \$b, \$c, &\$result, \$l1, \$l2, \$l3)
{
// Auxiliary variables
\$i = 0;
\$p1 = 0;
\$p2 = 0;
\$p3 = 0;
// This loop are combining sorted elements
while (\$i < \$l1 + \$l2 + \$l3)
{
if (\$p1 < \$l1 && \$p2 < \$l2 && \$p3 < \$l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (\$a[\$p1] < \$b[\$p2])
{
if (\$a[\$p1] < \$c[\$p3])
{
// Find smallest element in first array
\$result[\$i] = \$a[\$p1];
\$p1++;
}
else
{
// Find smallest element in third array
\$result[\$i] = \$c[\$p3];
\$p3++;
}
}
else if (\$b[\$p2] < \$c[\$p3])
{
// Find smallest element in second array
\$result[\$i] = \$b[\$p2];
\$p2++;
}
else
{
// Find smallest element in third array
\$result[\$i] = \$c[\$p3];
\$p3++;
}
}
else if (\$p1 < \$l1)
{
// When element exists in first array
if (\$p2 < \$l2)
{
// When element also exists in second array
if (\$a[\$p1] < \$b[\$p2])
{
\$result[\$i] = \$a[\$p1];
\$p1++;
}
else
{
\$result[\$i] = \$b[\$p2];
\$p2++;
}
}
else if (\$p3 < \$l3)
{
//  When element also exists in third array
if (\$a[\$p1] < \$c[\$p3])
{
\$result[\$i] = \$a[\$p1];
\$p1++;
}
else
{
\$result[\$i] = \$c[\$p3];
\$p3++;
}
}
else
{
// When element exists in only first array
\$result[\$i] = \$a[\$p1];
\$p1++;
}
}
else if (\$p2 < \$l2)
{
// When element exists in second array
if (\$p3 < \$l3)
{
// When element exists in third array
if (\$b[\$p2] < \$c[\$p3])
{
\$result[\$i] = \$b[\$p2];
\$p2++;
}
else
{
\$result[\$i] = \$c[\$p3];
\$p3++;
}
}
else
{
// When element exists in only second array
\$result[\$i] = \$c[\$p2];
\$p2++;
}
}
else
{
// When element exists in third array
\$result[\$i] = \$c[\$p3];
\$p3++;
}
\$i++;
}
}
// Display array elements
public	function printArr(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
echo("\n");
}
}

function main()
{
// Sorted Arrays
\$a = array(-2, 5, 7, 7, 10);
\$b = array(-4, 0, 1, 2, 3);
\$c = array(-1, -1, 2, 4, 5, 9);
// Get the size
\$l1 = count(\$a);
\$l2 = count(\$b);
\$l3 = count(\$c);
\$n = \$l1 + \$l2 + \$l3;
// Collecting resultant element
\$result = array_fill(0, \$n, 0);
// Merge
\$task->merge3SortedArray(\$a, \$b, \$c, \$result, \$l1, \$l2, \$l3);
// Display array elements
}
main();``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````/*
Node JS Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting
{
merge3SortedArray(a, b, c, result, l1, l2, l3)
{
// Auxiliary variables
var i = 0;
var p1 = 0;
var p2 = 0;
var p3 = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2++;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3++;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = b[p2];
p2++;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1++;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2++;
}
else
{
result[i] = c[p3];
p3++;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2++;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3++;
}
i++;
}
}
// Display array elements
printArr(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}

function main()
{
// Sorted Arrays
var a = [-2, 5, 7, 7, 10];
var b = [-4, 0, 1, 2, 3];
var c = [-1, -1, 2, 4, 5, 9];
// Get the size
var l1 = a.length;
var l2 = b.length;
var l3 = c.length;
var n = l1 + l2 + l3;
// Collecting resultant element
var result = Array(n).fill(0);
// Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
}
main();``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````#    Python 3 Program
#    Merge elements of three sorted arrays
#    In sorted order
class Sorting :
def merge3SortedArray(self, a, b, c, result, l1, l2, l3) :
#  Auxiliary variables
i = 0
p1 = 0
p2 = 0
p3 = 0
#  This loop are combining sorted elements
while (i < l1 + l2 + l3) :
if (p1 < l1 and p2 < l2 and p3 < l3) :
#  Case A
#  When element exists in all list (a,b,c)
#  Find smallest element
if (a[p1] < b[p2]) :
if (a[p1] < c[p3]) :
#  Find smallest element in first list
result[i] = a[p1]
p1 += 1
else :
#  Find smallest element in third list
result[i] = c[p3]
p3 += 1

elif (b[p2] < c[p3]) :
#  Find smallest element in second list
result[i] = b[p2]
p2 += 1
else :
#  Find smallest element in third list
result[i] = c[p3]
p3 += 1

elif (p1 < l1) :
#  When element exists in first list
if (p2 < l2) :
#  When element also exists in second list
if (a[p1] < b[p2]) :
result[i] = a[p1]
p1 += 1
else :
result[i] = b[p2]
p2 += 1

elif (p3 < l3) :
#   When element also exists in third list
if (a[p1] < c[p3]) :
result[i] = a[p1]
p1 += 1
else :
result[i] = c[p3]
p3 += 1

else :
#  When element exists in only first list
result[i] = a[p1]
p1 += 1

elif (p2 < l2) :
#  When element exists in second list
if (p3 < l3) :
#  When element exists in third list
if (b[p2] < c[p3]) :
result[i] = b[p2]
p2 += 1
else :
result[i] = c[p3]
p3 += 1

else :
#  When element exists in only second list
result[i] = c[p2]
p2 += 1

else :
#  When element exists in third list
result[i] = c[p3]
p3 += 1

i += 1

#  Display list elements
def printArr(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

def main() :
#  Sorted Arrays
a = [-2, 5, 7, 7, 10]
b = [-4, 0, 1, 2, 3]
c = [-1, -1, 2, 4, 5, 9]
#  Get the size
l1 = len(a)
l2 = len(b)
l3 = len(c)
n = l1 + l2 + l3
#  Collecting resultant element
result = [0] * (n)
#  Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3)
#  Display list elements

if __name__ == "__main__": main()``````

#### Output

``  -4  -2  -1  -1  0  1  2  2  3  4  5  5  7  7  9  10``
``````#    Ruby Program
#    Merge elements of three sorted arrays
#    In sorted order
class Sorting
def merge3SortedArray(a, b, c, result, l1, l2, l3)
#  Auxiliary variables
i = 0
p1 = 0
p2 = 0
p3 = 0
#  This loop are combining sorted elements
while (i < l1 + l2 + l3)
if (p1 < l1 && p2 < l2 && p3 < l3)
#  Case A
#  When element exists in all array (a,b,c)
#  Find smallest element
if (a[p1] < b[p2])
if (a[p1] < c[p3])
#  Find smallest element in first array
result[i] = a[p1]
p1 += 1
else

#  Find smallest element in third array
result[i] = c[p3]
p3 += 1
end

elsif (b[p2] < c[p3])
#  Find smallest element in second array
result[i] = b[p2]
p2 += 1
else

#  Find smallest element in third array
result[i] = c[p3]
p3 += 1
end

elsif (p1 < l1)
#  When element exists in first array
if (p2 < l2)
#  When element also exists in second array
if (a[p1] < b[p2])
result[i] = a[p1]
p1 += 1
else

result[i] = b[p2]
p2 += 1
end

elsif (p3 < l3)
#   When element also exists in third array
if (a[p1] < c[p3])
result[i] = a[p1]
p1 += 1
else

result[i] = c[p3]
p3 += 1
end

else

#  When element exists in only first array
result[i] = a[p1]
p1 += 1
end

elsif (p2 < l2)
#  When element exists in second array
if (p3 < l3)
#  When element exists in third array
if (b[p2] < c[p3])
result[i] = b[p2]
p2 += 1
else

result[i] = c[p3]
p3 += 1
end

else

#  When element exists in only second array
result[i] = c[p2]
p2 += 1
end

else

#  When element exists in third array
result[i] = c[p3]
p3 += 1
end

i += 1
end

end

#  Display array elements
def printArr(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

print("\n")
end

end

def main()
#  Sorted Arrays
a = [-2, 5, 7, 7, 10]
b = [-4, 0, 1, 2, 3]
c = [-1, -1, 2, 4, 5, 9]
#  Get the size
l1 = a.length
l2 = b.length
l3 = c.length
n = l1 + l2 + l3
#  Collecting resultant element
result = Array.new(n) {0}
#  Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3)
#  Display array elements
end

main()``````

#### Output

`````` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10
``````
``````/*
Scala Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting()
{
def merge3SortedArray(
a: Array[Int], b: Array[Int], c: Array[Int],
result: Array[Int], l1: Int, l2: Int, l3: Int): Unit = {
// Auxiliary variables
var i: Int = 0;
var p1: Int = 0;
var p2: Int = 0;
var p3: Int = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a(p1) < b(p2))
{
if (a(p1) < c(p3))
{
// Find smallest element in first array
result(i) = a(p1);
p1 += 1;
}
else
{
// Find smallest element in third array
result(i) = c(p3);
p3 += 1;
}
}
else if (b(p2) < c(p3))
{
// Find smallest element in second array
result(i) = b(p2);
p2 += 1;
}
else
{
// Find smallest element in third array
result(i) = c(p3);
p3 += 1;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a(p1) < b(p2))
{
result(i) = a(p1);
p1 += 1;
}
else
{
result(i) = b(p2);
p2 += 1;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a(p1) < c(p3))
{
result(i) = a(p1);
p1 += 1;
}
else
{
result(i) = c(p3);
p3 += 1;
}
}
else
{
// When element exists in only first array
result(i) = a(p1);
p1 += 1;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b(p2) < c(p3))
{
result(i) = b(p2);
p2 += 1;
}
else
{
result(i) = c(p3);
p3 += 1;
}
}
else
{
// When element exists in only second array
result(i) = c(p2);
p2 += 1;
}
}
else
{
// When element exists in third array
result(i) = c(p3);
p3 += 1;
}
i += 1;
}
}
// Display array elements
def printArr(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sorting = new Sorting();
// Sorted Arrays
var a: Array[Int] = Array(-2, 5, 7, 7, 10);
var b: Array[Int] = Array(-4, 0, 1, 2, 3);
var c: Array[Int] = Array(-1, -1, 2, 4, 5, 9);
// Get the size
var l1: Int = a.length;
var l2: Int = b.length;
var l3: Int = c.length;
var n: Int = l1 + l2 + l3;
// Collecting resultant element
var result: Array[Int] = Array.fill[Int](n)(0);
// Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
}
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``
``````import Foundation;
/*
Swift 4 Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting
{
func merge3SortedArray(_ a: [Int], _ b: [Int], _ c: [Int],
_ result: inout[Int], _ l1: Int, _ l2: Int, _ l3: Int)
{
// Auxiliary variables
var i: Int = 0;
var p1: Int = 0;
var p2: Int = 0;
var p3: Int = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1 += 1;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3 += 1;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2 += 1;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3 += 1;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1 += 1;
}
else
{
result[i] = b[p2];
p2 += 1;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1 += 1;
}
else
{
result[i] = c[p3];
p3 += 1;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1 += 1;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2 += 1;
}
else
{
result[i] = c[p3];
p3 += 1;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2 += 1;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3 += 1;
}
i += 1;
}
}
// Display array elements
func printArr(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
// Sorted Arrays
let a: [Int] = [-2, 5, 7, 7, 10];
let b: [Int] = [-4, 0, 1, 2, 3];
let c: [Int] = [-1, -1, 2, 4, 5, 9];
// Get the size
let l1: Int = a.count;
let l2: Int = b.count;
let l3: Int = c.count;
let n: Int = l1 + l2 + l3;
// Collecting resultant element
var result: [Int] = Array(repeating: 0, count: n);
// Merge
task.merge3SortedArray(a, b, c, &result, l1, l2, l3);
// Display array elements
}
main();``````

#### Output

``  -4  -2  -1  -1  0  1  2  2  3  4  5  5  7  7  9  10``
``````/*
Kotlin Program
Merge elements of three sorted arrays
In sorted order
*/
class Sorting
{
fun merge3SortedArray(
a: Array < Int > ,
b: Array < Int > ,
c: Array < Int > ,
result: Array < Int > ,
l1: Int, l2: Int, l3: Int): Unit
{
// Auxiliary variables
var i: Int = 0;
var p1: Int = 0;
var p2: Int = 0;
var p3: Int = 0;
// This loop are combining sorted elements
while (i < l1 + l2 + l3)
{
if (p1 < l1 && p2 < l2 && p3 < l3)
{
// Case A
// When element exists in all array (a,b,c)
// Find smallest element
if (a[p1] < b[p2])
{
if (a[p1] < c[p3])
{
// Find smallest element in first array
result[i] = a[p1];
p1 += 1;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3 += 1;
}
}
else if (b[p2] < c[p3])
{
// Find smallest element in second array
result[i] = b[p2];
p2 += 1;
}
else
{
// Find smallest element in third array
result[i] = c[p3];
p3 += 1;
}
}
else if (p1 < l1)
{
// When element exists in first array
if (p2 < l2)
{
// When element also exists in second array
if (a[p1] < b[p2])
{
result[i] = a[p1];
p1 += 1;
}
else
{
result[i] = b[p2];
p2 += 1;
}
}
else if (p3 < l3)
{
//  When element also exists in third array
if (a[p1] < c[p3])
{
result[i] = a[p1];
p1 += 1;
}
else
{
result[i] = c[p3];
p3 += 1;
}
}
else
{
// When element exists in only first array
result[i] = a[p1];
p1 += 1;
}
}
else if (p2 < l2)
{
// When element exists in second array
if (p3 < l3)
{
// When element exists in third array
if (b[p2] < c[p3])
{
result[i] = b[p2];
p2 += 1;
}
else
{
result[i] = c[p3];
p3 += 1;
}
}
else
{
// When element exists in only second array
result[i] = c[p2];
p2 += 1;
}
}
else
{
// When element exists in third array
result[i] = c[p3];
p3 += 1;
}
i += 1;
}
}
// Display array elements
fun printArr(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
// Sorted Arrays
val a: Array < Int > = arrayOf(-2, 5, 7, 7, 10);
val b: Array < Int > = arrayOf(-4, 0, 1, 2, 3);
val c: Array < Int > = arrayOf(-1, -1, 2, 4, 5, 9);
// Get the size
val l1: Int = a.count();
val l2: Int = b.count();
val l3: Int = c.count();
val n: Int = l1 + l2 + l3;
// Collecting resultant element
var result: Array < Int > = Array(n)
{
0
};
// Merge
task.merge3SortedArray(a, b, c, result, l1, l2, l3);
// Display array elements
}``````

#### Output

`` -4 -2 -1 -1 0 1 2 2 3 4 5 5 7 7 9 10``

## Time Complexity Analysis

The time complexity of this merging algorithm is proportional to the total number of elements across all three arrays, denoted by `n` (size of the merged array). The merging process involves a single comparison for each element, so the time complexity is O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post