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