# Merge two sorted array into a single sorted array

Upasana | October 16, 2020 | | 42 views

There are two sorted array of integers, you have to merge them both into single sorted array.

## Input

input
```a1 = {1, 2, 3, 6, 11}
a2 = {2, 4, 10}```
output
`o = {1, 2, 2, 3, 4, 6, 10, 11}`

## Approach

• Build a min-heap h of the k lists, using the first element as the key.

• While any of the lists is non-empty:

• Let i = find-min(h).

• Output the first element of list i and remove it from its list.

• Re-heapify h by adding more items from the list from which minimum element was removed.

## Implementation

In Java/Kotlin, we can construct a min-heap using PriorityQueue with ascending sorting order of its keys (we will retrieve smallest elements from min-heap when we poll)

First of all, we will create a holder class that will hold an element from a given array (a1 or a2)

PartitionArrayElement.kt
``````data class PartitionArrayElement(val item: Int,
val partition: Int)``````

Now we will write a logic that will take two or any number of input integer arrays (that have their elements sorted)

MergeSort.kt
``````import java.util.*

object MergeSort {

@JvmStatic
fun main(args: Array<String>) {
val x1: IntArray = intArrayOf(1, 2, 3, 6, 11)
val x2: IntArray = intArrayOf(2, 4, 10)
val output = compare(x1, x2)
println(output)
}

fun compare(vararg partitions: IntArray): ArrayList<Int> {
val output = ArrayList<Int>()
val partitionCurrentIndex: Array<Int> = Array(partitions.size) { 0 }    (1)

val minHeap = PriorityQueue<PartitionArrayElement>(partitions.size, compareBy { it.item })  (2)
partitions.forEachIndexed { index: Int, ints: IntArray ->       (3)
val item = PartitionArrayElement(ints[partitionCurrentIndex[index]], index)
partitionCurrentIndex[index] += 1
}
do {
val minItem = minHeap.poll()    (4)
if (minItem != null) {
println(minItem)
val partition = minItem.partition
if (partitions[partition].size > partitionCurrentIndex[partition]) {    (5)
val item = PartitionArrayElement(partitions[partition][partitionCurrentIndex[partition]], partition)
partitionCurrentIndex[partition] += 1
}
}
} while (minItem != null)
return output
}
}``````
 1 Keeps position of current element for each array. Once an element is processed, position will increment. 2 Min-Heap using PriorityQueue that will give us the minimum element when we use `poll()` method. 3 We seed the min-heap by taking first element from each input array. 4 We pull out the first element from min-heap, this is the minimum of all elements present in the min-heap. 5 We re-heapify the min-heap by adding elements from array from which element was removed in step 4

That’s all.

##### Top articles in this category:

###### Recommended books for interview preparation:
Book you may be interested in..
##### ebook PDF - Cracking Spring Microservices Interviews for Java Developers
Book you may be interested in..

##### Find more on this topic:

Java & Microservices interview refresher for experienced developers.