2

I am having some problems turning this solution from O(n^2) to O(n). Can anyone kindly help? I am not able to think of any ways to make the time complexity O(n).

//MERGE SORTED ARRAY
/*arr1 = [0,3,4,31]
arr2 = [4,6,30]*/
 
const mergeSortedArrays = (arr1, arr2) => {
  let arr = [];
  let flag = true;
 
  // MERGING ARRAYS
  for (let i = 0; i < arr1.length; i++) {
    arr.push(arr1[i]);//PUSHING ARRAY1 in arr
  }
  for (let i = 0; i < arr2.length; i++) {
    arr.push(arr2[i]);//PUSING ARRAY2 in arr
  }
 
  //SORTING ARRAYS
  while (flag) {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i + 1];
        arr[i + 1] = arr[i];
        arr[i] = temp;
        flag = true;
      } else {
        flag = false;
      }
    }
  }
 
  console.log(arr1);
  console.log(arr2);
  console.log(arr);//FINAL MERGED & SORTED ARRAY
  // return arr;
  
}
 
mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]);
Berthur
  • 4,300
  • 2
  • 14
  • 28
Soumyadeep Chatterjee
  • 19
  • 2
  • 1
    Is there any reason why not to use `Array.concat` and `Array.sort`? – Justinas May 20 '22 at 10:25
  • If both arrays are sorted, then you can just go over longer one (with additional var for the other ones index) and create 3rd array with sorted elements. If both arrays are not sorted, then only sorting algorithm that is O(n) is stalin sort. – Seti May 20 '22 at 10:30
  • `concat` then `sort` won't be O(n) because the sort is not O(n) – purple May 20 '22 at 10:38
  • Does this answer your question? [merge sorted arrays](https://stackoverflow.com/questions/5885891/merge-sorted-arrays) – Berthur May 20 '22 at 10:56

3 Answers3

2

Try visualising it. It is as if you had two sorted stacks of cards you wanted to sort. You can compare cards at the top of each stack, and put the smaller value on a third stack. And repeat until all cards are on the third sorted stack.

You can keep up two pointers, i and j, one for each array. This will emulate a stack.

The algorithm:

Repeat until the end of both arrays is reached:

   if arr1[i] <= arr2[j]

      push arr1[i] to the merged array and increment i

   else

      push arr2[j] to the merged array and increment j

And some javascript code:

let merged = [];
let i = 0;
let j = 0;
while(i < arr1.length || j < arr2.length){
    if(j == arr2.length || (i < arr1.length && arr1[i] <= arr2[j])){
        merged.push(arr1[i]);
        i++;
    } else{
        merged.push(arr2[j]);
        j++;
    }
}
Sophia Koulen
  • 302
  • 1
  • 7
1

You can use two pointer method (this solution is based on the assumption that the two lists will always be sorted):

let p1 = 0, p2 = 0;
let arr = [];

while (p1 < arr1.length && p2 < arr2.length) {
 if (arr1[p1] < arr2[p2])
   arr.push(arr1[p1++]);
 else
   arr.push(arr2[p2++]);
}

while (p1 < arr1.length)
 arr.push(arr1[p1++]);

while (p2 < arr2.length)
 arr.push(arr2[p2++]);

This code will run at the time complexity of O(N).

kelsny
  • 23,009
  • 3
  • 19
  • 48
Subash A
  • 13
  • 5
-1

Updated answer based on comments from using Array#sort() to:

const mergeSortedArrays = (arr1, arr2) => {
  const array = { arr1, arr2 }
  const index = { a1: 0, a2: 0 }
  const length = { a1: array.arr1.length, a2: array.arr2.length }
  const merged = []
  let current = 0

  while (current < length.a1 + length.a2) {
    const [a, i] =
      !(index.a1 >= length.a1) &&
      (index.a2 >= length.a2 || array.arr1[index.a1] < array.arr2[index.a2])
        ? ['arr1', 'a1']
        : ['arr2', 'a2']
    merged[current] = array[a][index[i]]
    index[i]++
    current++
  }

  return merged
}

const result = mergeSortedArrays([0, 3, 4, 31], [4, 6, 30])

console.log(result)
Yosvel Quintero
  • 18,669
  • 5
  • 37
  • 46
  • 3
    This is not technically O(n). You're using a sorting function again. So unless you know which sorting algorithm is used and can garantee that in this situation the complexity will be linear, i don't think this is the answer OP is looking for. – Sophia Koulen May 20 '22 at 10:39
  • If you want/need to sort an array recommended is to use `Array#sort()` – Yosvel Quintero May 20 '22 at 10:45
  • 1
    @YosvelQuinteroArguelles Though a proper description of OP's problem is missing in their question, it looks to me as if they only need to `mergeSortedArrays`, not in fact perform any sorting. – Berthur May 20 '22 at 10:50
  • 1
    The confusion, I imagine, comes from OP's proposed O(n^2) solution where they just dump it all in an array and throw a sorting algorithm on it, which indeed solves the problem but is naturally not the best way of performing a merge. – Berthur May 20 '22 at 10:53
  • 1
    Yep, thank you for the comments.. I have missed that detail – Yosvel Quintero May 20 '22 at 10:53