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)
    {
        Sorting task = new Sorting();
        // 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
        task.printArr(result, n);

    }
}

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()
{
	Sorting *task = new Sorting();
	// 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
	task->printArr(result, n);
	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)
	{
		Sorting task = new Sorting();
		// 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
		task.printArr(result, n);
	}
}

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()
{
	$task = new Sorting();
	// 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
	$task->printArr($result, $n);
}
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()
{
	var task = new Sorting();
	// 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
	task.printArr(result, n);
}
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() :
	task = Sorting()
	#  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
	task.printArr(result, n)

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() 
	task = Sorting.new()
	#  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
	task.printArr(result, n)
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
		task.printArr(result, n);
	}
}

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()
{
	let task: Sorting = Sorting();
	// 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
	task.printArr(result, n);
}
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
{
	val task: Sorting = Sorting();
	// 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
	task.printArr(result, n);
}

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.

New Comment