Merge sorted lists

Question:
n lists, each is sorted, each has size m
merge into one sorted list, overall size n*m

Easy Solution:
1. Pointers pointing to each position of the array
2. Compare the element at the positions
3. Find the minimum and insert in the outputArray

Complexity
1. Traverse all the lists (n*m)
2. Comparisons to find the minimum element ((n-1) comparisons) 
O((n*m)(n-1)) = O(n^2*m)

MinHeap heap = new MinHeap();

// $inList[n] - Input Lists
$outputArr = array();

// Push first elements of all the lists in the MinHeap
for (int i=0; i<n; i++)
{
    heap.push(i, array_pop($inList[i]));
}   

/*
  1. Pop element from MinHeap
  2. Push the next element from the inList from which the element was pop'd
  3. Do this till the MinHeap is empty  
*/
$popObj = heap.pop();
while (!empty($popObj))
{
    $listId = $popObj["listId"];
    $elementPop = $popObj["leastElement"];
   
    $outputArr[] = $elementPop;
    heap.push($listId, array_pop($inList[$listId]));
}

// Complexity
1. n-size heap
2. log n to insert in heap
3. O(n*m*logn)