Introduction

Given k sorted arrays of size n each, merge them and print the sorted output.

Input:
k = 3, n = 4
arr[][] = { 
    {1, 3, 5, 7},
    {2, 4, 6, 8},
    {0, 9, 10, 11}
} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11
Explanation: The output array is a sorted array that contains all the elements of the input matrix.

Approach

We think of the Merge operation in the Merge Sort to merge two sorted arrays into one. We can optimize this approach by merging in the pair and merge till it converges to a single array.

Sample Example for the Merge Approach
Also known as divide and conquer merge in the batches of two
Main Merge method
Helper Merge method
Time Complexity

We can also use the Min Heap method to sort batches of k elements repeating n times. This will reduce the Space complexity to O(k)

The below problem approach might consists of minor coding issues that are resolved in the implementation in the end.

Min Heap Node and Enqueue Method in the MinHeap
MinHeap Dequeue and BubbleUp methods
Main Merge method (needs code changes to use the MinHeapNode refer the implementation below) and Trickle down

The below implementation consists of a Min Heap implementation.

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    internal class MergeKSortedArrays
    {
        public static void Run()
        {
            var input = new[]
            {
                new[] {1, 3, 5, 7},
                new[] {2, 4, 6, 8},
                new[] {0, 9, 10, 11}
            };
            var res = Merge(input);
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }

        private static int[] Merge(int[][] input)
        {
            var k = input.Length;
            var mh = new MinHeap<MinHeapNode>(k);
            var res = new List<int>();

            // Initialize
            var firstIndex = 0;
            for (var j = 0; j < k; j++)
            {
                var n = input[j].Length;
                if (firstIndex >= n)
                {
                    continue;
                }
                mh.Enqueue(new MinHeapNode
                {
                    Val = input[j][firstIndex],
                    KIndex = j,
                    NextNIndex = firstIndex + 1
                });
            }

            while (mh.Count > 0)
            {
                var node = mh.Dequeue();
                res.Add(node.Val);
                if (node.NextNIndex >= input[node.KIndex].Length)
                {
                    continue;
                }
                node.Val = input[node.KIndex][node.NextNIndex++];
                mh.Enqueue(node);
            }

            return res.ToArray();
        }
    }

    internal class MinHeapNode : IComparable<MinHeapNode>
    {
        public int Val { get; set; }
        public int KIndex { get; set; }
        public int NextNIndex { get; set; }

        public int CompareTo(MinHeapNode other)
        {
            if (ReferenceEquals(this, other)) return 0;
            if (ReferenceEquals(null, other)) return 1;
            return Val.CompareTo(other.Val);
        }
    }

    internal class MinHeap<T> where T : IComparable<T>
    {
        private readonly T[] _nodes;

        public MinHeap(int k)
        {
            _nodes = new T[k];
            Count = 0;
        }

        public int Count { get; private set; }

        public void Enqueue(T node)
        {
            if (Count >= _nodes.Length)
            {
                throw new OverflowException($"Heap is full: {Count}");
            }

            _nodes[Count++] = node;
            BubbleUp(Count - 1);
        }

        public T Dequeue()
        {
            if (Count <= 0)
            {
                throw new IndexOutOfRangeException($"Heap is empty : {Count}");
            }

            var index = 0;
            var front = _nodes[index];
            _nodes[index] = _nodes[--Count];
            TrickleDown(index);
            return front;
        }

        private void TrickleDown(int index)
        {
            var childIndex = GetLesserChildIndex(index);
            while (index <= _nodes.Length - 1 && childIndex > -1 && childIndex < Count && _nodes[index].CompareTo(_nodes[childIndex]) > -1)
            {
                Swap(index, childIndex);
                index = childIndex;
                childIndex = GetLesserChildIndex(index);
            }
        }

        private int GetLesserChildIndex(in int index)
        {
            var childIndex = GetChildIndex(index);
            if (childIndex == -1 || childIndex >= _nodes.Length - 1)
            {
                return -1;
            }

            return _nodes[childIndex + 1].CompareTo(_nodes[childIndex]) < 0
                ? childIndex + 1
                : childIndex;
        }

        private int GetChildIndex(in int index)
        {
            if (index >= _nodes.Length - 1)
            {
                return -1;
            }

            return index * 2 + 1;
        }

        private void BubbleUp(int index)
        {
            var parentIndex = GetParent(index);
            while (parentIndex > -1 && index > 0 && _nodes[parentIndex].CompareTo(_nodes[index]) > 0)
            {
                Swap(parentIndex, index);
                index = parentIndex;
                parentIndex = GetParent(index);
            }
        }

        private void Swap(in int parentIndex, in int index)
        {
            var temp = _nodes[index];
            _nodes[index] = _nodes[parentIndex];
            _nodes[parentIndex] = temp;
        }

        private int GetParent(in int index)
        {
            if (index == 0)
            {
                return -1;
            }
            return (index - 1) / 2;
        }
    }
}
Program with the Min Heap implementation