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)
            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 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:
  1. find single repeating number from a big array
  2. How will you find out first non-repeating character from a string
  3. Morgan Stanley Java Interview Questions
  4. Cracking core java interviews - question bank
  5. Citibank Java developer interview questions
  6. Multi-threading Java Interview Questions for Investment Bank
  7. ION Trading Java Interview Questions

Recommended books for interview preparation:

Find more on this topic:
Buy interview books

Java & Microservices interview refresher for experienced developers.