DEV Community

Patrick Obafemi
Patrick Obafemi

Posted on • Updated on

Data Structures And Algorithms For Not So 'Algorithmic' Languages 2: Merge Sorted Array(Easy)

Hello everyone and I'm glad you are here. In our last post we did a basic intro to what algorithms are and what we aim to achieve with this thread. Today we will be looking at our first algorithm and that is the merge sorted algorithm.
In this algorithm you're given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Basically you are to fill the first array up in non descending order with the values of nums1 and nums2.

The easiest approach is to add the nums2 array value to the end of the array and use a sort function to sort them but that is an O(klogk) where k is the value of m + n. An optimal solution is to use the two pointer approach. Just add a pointer to the last element of nums1 and another to nums2 and compare the values. Add the higher value to the end of nums1 array and decrement the pointer of the array with the highest value.

here is the javascript code

    var merge = function(nums1, m, nums2, n) {
    p1 = m - 1; p2 = n - 1; i = m + n - 1;
    while(p2 >= 0) {
        if(p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[i--] = nums1[p1--];
            } else {
                nums1[i--] = nums2[p2--];
            }
        }
    };
Enter fullscreen mode Exit fullscreen mode


`

And the php implementation

`

     function merge(&$nums1, $m, $nums2, $n) {
        $p1 = $m - 1; $p2 = $n - 1; $i = $m + $n - 1;
        while($p2 >= 0) {
            if($p1 >= 0 && $nums1[$p1] > $nums2[$p2]) {
                $nums1[$i--] = $nums1[$p1--];
            } else {
                $nums1[$i--] = $nums2[$p2--];
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode


`

So in our next post we will look at a medium difficulty question. If you got any questions or contributions hit me up in the comments. Happy coding!

Top comments (0)