# Merge k Sorted Arrays

• Input is k sorted arrays in the form of a 2D matrix (int[][] int Java). Output should be a single sorted array in the form of either array or ArrayList.

• This solution will assume all arrays are of the same size, it could be modified to accept a list of arrays which size is not necessarily the same.
this implementation will keep duplicated items, it could be modified to remove duplicated items.

for each array it will add the elements on an ordered list, then the list is turned into an array

I added a simple test to validate the algorithm

``````using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace AlgorithmsTests
{
[TestClass]
public class MergeKSortedArrays
{
[TestMethod]
public void MergeKSortedArrays_Test()
{
//define the arrays
int[][] arr = new int[][]
{
new int[] { 2, 5 ,8 ,12},
new int[] { 4, 9 ,22, 23},
new int[] { 2, 105, 106,1000}
};

Assert.IsTrue(AreArraysEqual(
new int[] { 2, 2, 4, 5, 8, 9, 12, 22, 23, 105, 106, 1000 },
MergeArrays(arr)));
}

private int[] MergeArrays(int[][] arr)
{
if (arr == null)
{
return null;
}

for (int i = 0; i < arr.Length; i++)
for (int j = 0; j < arr[i].Length; j++)
{
}

return list.ToArray();
}

//compare each item on the array ( for validation)
private bool AreArraysEqual(int[] a, int[] b)
{
if (a.Length != b.Length)
return false;
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i])
{
return false;
}
}
return true;
}

{
private int size = 0;
{
while (p != null && p.Value < value)
{
prev = p;
p = p.Next;
}
if (prev != null)
{
//not the first element inserti it
prev.Next = c;
}
else
{
}
c.Next = p;
//keep track of the size for later
size++;
}

public int[] ToArray()
{
int[] arr = new int[size];

// add each one in order to the new array
int i = 0;
while (p != null)
{
arr[i++] = p.Value;
p = p.Next;
}
return arr;
}
}

{
public int Value;
}
}
}
``````

• Minheap can be used to store the k top elements. Extract min element from the heap and then replace it by a next element of an array whose element was minimum last time. Then Heapify it. Do this for all the elements.
Time Complexity: O(nlog(k))

• If you convert 2D list to 1d list and apply mergeSort it will print sorted 1D list, time complexity : O(n log n)

``````#Typical Merge Sort
def mergeSort(mlist):
result = []
mlen = len(mlist)
if mlen < 2:
return mlist

# split until left and right are single element list
mid = mlen // 2
l = mergeSort(mlist[:mid])
r = mergeSort(mlist[mid:])

i = 0
j = 0

while i < len(l) and j < len(r):
if l[i] > r[j]:
result.append(r[j])
j += 1
else:
result.append(l[i])
i += 1

result += l[i:]
result += r[j:]

return result

d = [
[1,3,2,5],
[9,8,3],
[4,9,11,6,1]
]
argList = []
for di in d:
argList += di

ans = mergeSort(argList)
print(ans)
``````

• it seems this code is more easy to understand. column is an array to save the position of every row index.

``````static List<Integer> mergeKSortedArray(int[][] arr) {
List<Integer> res = new ArrayList<>(arr.length * arr[0].length);
int[] column = new int[arr.length];

boolean changed = true;
while(changed) {
changed = false;
int min = Integer.MAX_VALUE;
int minRow = -1;
for (int i = 0; i < arr.length; i++) {
if (column[i] < arr[i].length && arr[i][column[i]] < min) {
min = arr[i][column[i]];
minRow = i;
changed = true;
}
}
if (changed) {
column[minRow]++;
}
}

return res;
}
``````

• I think flatten out the 2D matrix and sort it is a better solution than using Min Heap or Priority Queue.

O(NlogN) vs O(Nlogk) is not a big difference, but the implementation is much simpler

log2(10_000_000) = 23 vs. log2(10) = 3

Very simple implementation in Ruby

``````a.flatten.sort
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.