During a programming interview, the employer may ask you to demonstrate your ability to work with more complex coding functions, such as merging arrays.

Approach 1:

• To merge two arrays, you can create a new array of size equal to the sum of two arrays. After that, you can copy the ELEMENTS from the first array into the new one. Then you can traverse the second array and INSERT elements from it into the new one using insertion sort.This method takes
  • Time complexity: O(n1 * n2)
  • Extra Space: O(n1+n2) .

Approach 2 using Heap:

• Convert the second array to min-heap:
  • As you traverse the first array, compare the current ELEMENT to the top of the created min_heap.
  • In this case, if the current element in the first array is greater than the heap top, swap the current element of the first array with the ROOT of the heap, and heapify the root of the min_heap.
  • The first array now contains the N first elements of the sorted merged array after PERFORMING the above operation for every element of the first array.
• Now, the last M elements of the sorted merged array are in the min_heap or second array.
• Apply in-place heapsort to the second array to sort them.
  • Time Complexity: O(N*logM + M*logN)
  • Extra Space: O(1)