a1 = {1, 2, 3, 6, 11} a2 = {2, 4, 10}
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
o = {1, 2, 2, 3, 4, 6, 10, 11}
Approach

Build a minheap h of the k lists, using the first element as the key.

While any of the lists is nonempty:

Let i = findmin(h).

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

Reheapify h by adding more items from the list from which minimum element was removed.

Implementation
In Java/Kotlin, we can construct a minheap using PriorityQueue with ascending sorting order of its keys (we will retrieve smallest elements from minheap when we poll)
First of all, we will create a holder class that will hold an element from a given array (a1 or a2)
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)
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)
minHeap.add(item)
partitionCurrentIndex[index] += 1
}
do {
val minItem = minHeap.poll() (4)
if (minItem != null) {
println(minItem)
output.add(minItem.item)
val partition = minItem.partition
if (partitions[partition].size > partitionCurrentIndex[partition]) { (5)
val item = PartitionArrayElement(partitions[partition][partitionCurrentIndex[partition]], partition)
minHeap.add(item)
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  MinHeap using PriorityQueue that will give us the minimum element when we use poll() method. 
3  We seed the minheap by taking first element from each input array. 
4  We pull out the first element from minheap, this is the minimum of all elements present in the minheap. 
5  We reheapify the minheap by adding elements from array from which element was removed in step 4 
That’s all.
Top articles in this category:
 find single repeating number from a big array
 How will you find out first nonrepeating character from a string
 Morgan Stanley Java Interview Questions
 Cracking core java interviews  question bank
 Citibank Java developer interview questions
 Multithreading Java Interview Questions for Investment Bank
 ION Trading Java Interview Questions