a1 = {1, 2, 3, 6, 11} a2 = {2, 4, 10}
Merge two sorted array into a single sorted array
Carvia Tech  October 16, 2020   0 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
 BlackRock Top Java Interview Questions: Investment Banking Domain
 Multithreading Java Interview Questions for Investment Bank
Find more on this topic:
Java Interviews
Interview  Product Companies, eCommerce Companies, Investment Banking, Healthcare Industry, Service Companies and Startups.
Last updated 1 week ago
Recommended books for interview preparation:
Similar Posts
 Merge two sorted array into a single sorted array
 Spring Boot with GMAIL SMTP
 Mandrill emails in Spring Boot Java
 Hibernate & Spring Data JPA interview questions
 Generating cryptographically strong key/secret in Java
 Reverse the bits of a number and check if the number is palindrome or not
 MD5 and SHA256 in Java Kotlin and Android
 There is no PasswordEncoder mapped for the id
 Interthread communication in Java
 What are different thread states in Java