CODEWITHSUNDEEP
javascript
Amit Modi
Amit Modi

Reputation: 137

how to merge two sorted array in one sorted array in JavaScript without using sort()

In this program merged two array and then sorted using temp.but this not correct method.because two array are sorted ,so method should be unique i.e. merging of two sorted in sorted form should be unique.

Example:

function mergeSortdArray(a,b){
	for(var i=0;i<b.length;i++){
		a.push(b[i]);
	}
	//console.log(a);
for(i=0;i<a.length;i++)
    {
        for(j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));

Upvotes: 10

Views: 36226

Answers (30)

Parth Raval
Parth Raval

Reputation: 4423

var a = [1, 2, 3, 5, 9, 11]
var b = [4, 6, 7, 8]
var c = [];

function mergeArr() {
  for (let i = 0; i < b.length; i++) {
    for (let j = 0; j < a.length; j++) {
      if (!c.includes(b[i])) {
        c.push(b[i]);
      }
      if (!c.includes(a[j])) {
        c.push(a[j]);
      }
    }
  }
  organizeArr(c)
}

function organizeArr() {
  let organizer;
  for (let index = 0; index < c.length; index++) {
    for (let j = index + 1; j < c.length; j++) {
      if (c[index] > c[j]) {
        organizer = c[index]
        c[index] = c[j]
        c[j] = organizer
      }
    }
  }
  console.log(c);

}
mergeArr()

First Merge Array and then sort array which returns this function can be scalable up to n number

Upvotes: 0

Amit Vishwakarma
Amit Vishwakarma

Reputation: 316

Please find the below solution. Stackblitz link - https://stackblitz.com/edit/js-mp1ajm?file=index.js

class MergeSortArray {
  arr1 = [];
  arr2 = [];
  arr3 = [];

  constructor(arr1, arr2) {
    this.arr1 = arr1;
    this.arr2 = arr2;
  }

  mergeArray() {
    let n1 = this.arr1.length;
    let n2 = this.arr2.length;
    let i = 0,
      j = 0,
      k = 0;
    while (i < n1 && j < n2) {
      if (this.arr1[i] < this.arr2[j]) {
        this.arr3[k++] = this.arr1[i++];
      } else {
        this.arr3[k++] = this.arr2[j++];
      }
    }

    // Store remaining elements of first array
    while (i < n1) this.arr3[k++] = this.arr1[i++];

    // Store remaining elements of second array
    while (j < n2) this.arr3[k++] = this.arr2[j++];

    return this.arr3;
  }
}
let obj = new MergeSortArray([1, 3, 5, 7, 9, 67], [2, 4, 6, 8]);
let arr3 = obj.mergeArray();
console.log(arr3)

Upvotes: 0

Ashish
Ashish

Reputation: 2068

Merge two sorted arrays in JavaScript

var SortedArrays = function(nums1, nums2) {
    let array = [];
    let leftIndex = 0, rightIndex = 0;
    while(leftIndex < nums1.length && rightIndex < nums2.length) {
        if(nums1[leftIndex] < nums2[rightIndex]) {
            array.push(nums1[leftIndex]);
            leftIndex++;
        } else {
            array.push(nums2[rightIndex]);
            rightIndex++;
        }
    }
    array = array.concat(nums1.slice(leftIndex)).concat(nums2.slice(rightIndex));
    return array;
}

Upvotes: 2

Priya Nayak
Priya Nayak

Reputation: 47

console.log("merge sorted array::", mergeBinaryArray([1,4,5,34,36],  [2,4,5,6,7,8]))
function mergeBinaryArray(array1, array2){
let p1 = 0, p2= 0, p3 =0, sortedArray = []; 
while( p1 < array1.length && p2 < array2.length){
    if(array1[p1] < array2[p2]){
        sortedArray[p3] = array1[p1]
        p1++;
        p3++
    }else{
        sortedArray[p3] = array2[p2]
        p2++;
        p3++;
    }

}
if(p1 < array1.length){
   for(let index = p1; index < array1.length; index++){
       sortedArray.push(array1[index]);
       p3++
   }

}
if(p2 < array2.length){
   for(let index= p2; index< array2.length; index++){
       sortedArray.push(array2[index]);
       p3++;
   }
   
}
return sortedArray;
}

Upvotes: 0

Nosheen Rashid
Nosheen Rashid

Reputation: 1

function mergeSortdArray(a,b){
    for(var i=0;i<b.length;i++){
        a.push(b[i]);
    }
    //console.log(a);
for(i=0;i<a.length;i++)
    {
        for(j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
console.log(mergeSortdArray([1,2,3,5,9],[4,6,7,8]));

Upvotes: 0

arpanexe
arpanexe

Reputation: 60

Solution for merging two sorted array with Time complexity and space complexity of O(n)

Most of the answers are correct but they have ignored equal value comparison

function merge(arr1, arr2) {
  let index1 = 0
  let index2 = 0
  const mergedArray = []
  while (index1 < arr1.length || index2 < arr2.length) {
    if (arr1[index1] < arr2[index2] || index2 === arr2.length) {
      mergedArray.push(arr1[index1])
      index1++
    } else if (arr1[index1] > arr2[index2] || index1 === arr1.length) {
      mergedArray.push(arr2[index2])
      index2++
    } else if (arr1[index1] === arr2[index2]) {
      mergedArray.push(arr1[index1])
      mergedArray.push(arr2[index2])
      index1++
      index2++
    }
  }
  return mergedArray
}

console.log(JSON.stringify(merge([1, 3, 5, 7, 8, 9, 10], [2, 4, 6, 11, 12])))

Upvotes: 0

Amit Vishwakarma
Amit Vishwakarma

Reputation: 316

Here is the code to merge two sorted array in javascript.

class MergeSortArray {
  arr1 = [];
  arr2 = [];
  arr3 = [];

  constructor(arr1, arr2) {
    this.arr1 = arr1;
    this.arr2 = arr2;
  }

  mergeArray() {
    let n1 = this.arr1.length;
    let n2 = this.arr2.length;
    let i = 0,
      j = 0,
      k = 0;
    while (i < n1 && j < n2) {
      if (this.arr1[i] < this.arr2[j]) {
        this.arr3[k++] = this.arr1[i++];
      } else {
        this.arr3[k++] = this.arr2[j++];
      }
    }

    // Store remaining elements of first array
    while (i < n1) this.arr3[k++] = this.arr1[i++];

    // Store remaining elements of second array
    while (j < n2) this.arr3[k++] = this.arr2[j++];

    return this.arr3;
  }
}
let obj = new MergeSortArray([1, 3, 5, 7, 9, 11], [2, 4, 6, 8]);
let arr3 = obj.mergeArray();
console.log(arr3);

You can find the code in StackBlitz editor here : Merge two sorted array

Upvotes: 0

mikedavies-dev
mikedavies-dev

Reputation: 3345

Merge N sorted arrays

Based on Dovev Hefetz's answer (https://stackoverflow.com/a/48147806/1167223) but supports N arrays and accepts sortFn as an attribute

function mergeArrays(arrays, sortFn) {
  return arrays.reduce(function mergeArray(arrayA, arrayB, index) {
    // For the first iteration return the first array
    if (index === 0) {
      return arrayA;
    }

    const sorted = [];
    let indexA = 0;
    let indexB = 0;

    while (indexA < arrayA.length && indexB < arrayB.length) {
      if (sortFn(arrayA[indexA], arrayB[indexB]) > 0) {
        sorted.push(arrayB[indexB++]);
      } else {
        sorted.push(arrayA[indexA++]);
      }
    }
  
    // Add any remaining entries
    if (indexB < arrayB.length) {
      return sorted.concat(arrayB.slice(indexB));
    } else {
      return sorted.concat(arrayA.slice(indexA));
    };
  }, arrays[0]);
}

Example use

const merged = mergeArrays([
  [0, 1, 2, 3, 4, 5, 6],
  [0, 1, 2, 3, 3, 5, 5, 6],
  [0, 0, 2, 3, 4, 5, 6]
], (v1, v2) => v1 - v2);

console.log(merged);

/*
Results:
[
  0, 0, 0, 0, 1, 1, 2,
  2, 2, 3, 3, 3, 3, 4,
  4, 5, 5, 5, 5, 6, 6,
  6
]
*/

Upvotes: 0

Sarwar Sateer
Sarwar Sateer

Reputation: 465

Here is my simple code to achieve this goal:

function mergeSortetArrays(array1, array2) {
const mergedArray = []; //This is const, we don't have to change the type of this array
let array1Item = array1[0];// We use let, because it will store undefined
let array2Item = array2[0];
let i = 1;
let j = 1;

//check input
if(array1.length === 0)
    return array2;
if(array2.length === 0)
    return array1;

//loop through each array, and store to the mergedArray
    while( array1Item || array2Item) {
       console.log(array1Item, array2Item);
        if (!array2Item || array1Item < array2Item) {
            mergedArray.push(array1Item);
            array1Item = array1[i]
            i++;
            } else {
                mergedArray.push(array2Item);
                array2Item = array2[j];
                j++;
         }
   }
   return mergedArray;
 }

console.log(mergeSortetArrays([0, 1, 3, 5,7,8, 8], [1, 2, 3, 4, 6, 7]))

Upvotes: 0

Apetu Gideon
Apetu Gideon

Reputation: 136

Try this out.

function mergeSortedArrays(a, b) {
    //Setting up the needed variables
    let mergedArray = [], aIndex = 0, bIndex = 0, 
        mergedIndex = 0, aCount = a.length, 
        bCount = b.length;
        
    //Loop until all items from the array merges in
    while (mergedIndex < (aCount + bCount)) {
        mergedArray[mergedIndex++] = (a[aIndex] < b[bIndex]) ? a[aIndex++] : b[bIndex++];
    }
    return mergedArray;
}
    mergeSortedArrays([1, 3, 5, 7, 9], [2, 4, 6, 8, 10, 20, 30, 40]);

Upvotes: 0

Annis Tan
Annis Tan

Reputation: 1

In case using the built in sorted method is not allowed:

function mergeSortedArrays(a, b) {
   let storage = [];
   let aLen = a.length;
   let bLen = b.length;
   let i = 0;
   let j = 0;

   while(i < aLen || j < bLen){ 
     if(a[i] < b[j]){
       storage.push(a[i]);
       i++;
     }
     else if(a[i] >= b[j]){
       storage.push(b[j]);
       j++;
     }
     else if(a[i] === undefined){
       storage.push(b[j]);
       j++;
     }
     else if(b[j] === undefined){
       storage.push(a[i]);
       i++;
     }
   }
   return storage
}

If using sorted method is allowed, this is much better:

function mergeSortedArrays(a, b){
   let result = a.concat(b);  //concat both arrays into one first
   return result.sort((a,b) => a - b)  //then sort the concated array
}

Upvotes: 0

Keshav Gera
Keshav Gera

Reputation: 11244

now you can do with es6 (...)spread operator

========================================
   using es6 (...)spread operator
========================================
let a=[1,2,3,5,9]
let b=[4,6,7,8]

let sortedArray=[...a,...b].sort()
console.log(sortedArray) 

outputy :- [1, 2, 3, 4, 5, 6, 7, 8, 9]

========================================
       2nd way 
========================================


function mergeSortedArray(a, b) {
    var sortedArray = [], indexA = 0, indexB = 0;

    while (indexA < a.length && indexB < b.length) {
        if (sortFuntion(a[indexA], b[indexB]) > 0) {
            sortedArray.push(b[indexB++]);
        } else {
            sortedArray.push(a[indexA++]);
        }
    }

    if (indexB < b.length) {
        sortedArray = sortedArray.concat(b.slice(indexB));
    } else {
        sortedArray = sortedArray.concat(a.slice(indexA));
    }

    return sortedArray;
}

function sortFuntion(a, b) {
    return a - b;
}

console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));
output :- 1,2,3,4,5,6,7,8,9

Upvotes: 1

Siva Rajesh
Siva Rajesh

Reputation: 71

// Everything fine but small mistake down there

function sortedArray(a,b){
    for(var i=0;i<b.length;i++){
        a.push(b[i]);
    }
    //console.log(a);
for(i=0;i<a.length;i++)
    {
        for(j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    
    //<!--You did a mistake here you have loop through for to get array elements-->
    for(i=0;i<a.length;i++){
    return a;
    }
}
console.log(sortedArray([1,2,3,5,9],[4,6,7,8]));

Upvotes: 0

Abhishek Gautam
Abhishek Gautam

Reputation: 1767

It may not be the cleanest approach but give it a try.

function mergeSortedArrays(array1, array2){
  const mergedArray = [];
  let array1Item = array1[0];
  let array2Item = array2[0];
  let i = 1;
  let j = 1;
 
  if(array1.length === 0) {
    return array2;
  }
  if(array2.length === 0) {
    return array1;
  }

  while (array1Item || array2Item){
   if(array2Item === undefined || array1Item < array2Item){
     mergedArray.push(array1Item);
     array1Item = array1[i];
     i++;
   }   
   else {
     mergedArray.push(array2Item);
     array2Item = array2[j];
     j++;
   }
  }
  return mergedArray;
}

mergeSortedArrays([0,3,4,31], [3,4,6,30]);

Upvotes: 0

Ranjeet Kumar
Ranjeet Kumar

Reputation: 11

I have been working on it for while now, and I have found a good solution. I didn't came up with this algorithm, but I implemented it properly in Javscript. I have tested it with massive number of array, and I have included comments so it's easier to understand. Unlike many other solutions, this one of the most efficient one, and I have included some tests. You run the code to verify that works. Time Complexity of a this solution is O(n)

function mergeTwoSortedArraay(rightArr, leftArr) {
 // I decided to call frist array "rightArr" and second array "leftArr"
  var mergedAr = [], sizeOfMergedArray = rightArr.length + leftArr.length; // so if rightArray has 3 elements and leftArr has 4, mergedArray will have 7.
   var r = 0, l =0; // r is counter of rightArr and l is for leftArr;
   for(var i =0; i< sizeOfMergedArray; ++i) {
       if(rightArr[r] >= leftArr[l] || r >= rightArr.length) { // r >= rightArr.length when r is equal to greater than length of array, if that happens we just copy the reaming 
        // items of leftArr to mergedArr

            mergedAr[i] = leftArr[l];
            l++;
       } else { 
           mergedAr[i] = rightArr[r];
           r++;
       }
   }
   return mergedAr;
}
// few tests
console.log(mergeTwoSortedArraay([ 0, 3, 4, 7, 8, 9 ],[ 0, 4, 5, 6, 9 ]));

console.log(mergeTwoSortedArraay([ 7, 13, 14, 51, 79 ],[ -356, 999 ]));
console.log(mergeTwoSortedArraay([ 7, 23, 64, 77 ],[ 18, 42, 45, 90 ]));

Upvotes: 0

vipin joshi
vipin joshi

Reputation: 57

function mergeSortedArray(a, b){
var merged = [], 
aElm = a[0],
  bElm = b[0],
  i = 1,
  j = 1;
 if(a.length ==0)
   return b;
     if(b.length ==0)
       return a;
      while(aElm || bElm){
        if((aElm && !bElm) || aElm < bElm){
           merged.push(aElm);
              aElm = a[i++];
         }   
         else {
                merged.push(bElm);
                bElm = b[j++];
              }
      }
      return merged;
    }
    
   //check

 > mergeSortedArray([2,5,6,9], [1,2,3,29]);
 = [1, 2, 2, 3, 5, 6, 9, 29]

hope this helps, please correct me if i am wrong anywhere.

Upvotes: 0

Mohit Singh Negi
Mohit Singh Negi

Reputation: 54

let Array1 = [10,20,30,40];
let Array2 = [15,25,35];
let mergeArray=(arr1, arr2)=>{
    for(var i = arr2.length-1; i>= 0; i--){
        let curr1 = arr2[i]
        for(var j = arr1.length-1; j>= 0; j--){
            let curr2 = arr1[j]
            if(curr1<curr2){
                arr1[j+1]  = curr2
            }else{
                arr1[j+1]  = curr1
                break;
            }
        }
    }
    return arr1
}

mergeArray(Array1, Array2)

Upvotes: 0

xdeepakv
xdeepakv

Reputation: 8135

Fastest Merge of 2 Sorting array

function merge(a, b) {
  let i = 0,
    j = 0;
  let array = [];
  let counter = 0;
  while (i < a.length && j < b.length) {
    if (a[i] > b[j]) array[counter++] = b[j++];
    else if (a[i] < b[j]) array[counter++] = a[i++];
    else (array[counter++] = a[i++]), j++;
  }
  while (j < b.length) {
    array[counter++] = b[j++];
  }
  while (i < a.length) {
    array[counter++] = a[i++];
  }
  return array;
}
console.log(merge([1, 3], [2, 4, 5]));

console.log(merge([1, 3, 123, 125, 127], [2, 41, 50]));

Upvotes: 0

George I. Tsopouridis
George I. Tsopouridis

Reputation: 273

Please find here also an implementation for merging two sorted Arrays. Actually, we could compare one by one the Array items pushing them to a new Array and when we parse completely one Array, we just concat the sliced part of the second already sorted Array.

const merge = (arr1, arr2) => {
    let arr = [];
    let i = 0;
    let j = 0;
    while (i < arr1.length || j < arr2.length) {
        if (i === arr1.length) {
            return arr.concat(arr2.slice(j));
        }
        if (j === arr2.length) {
            return arr.concat(arr1.slice(i));
        }
        if (arr1[i] < arr2[j]) {
            arr.push(arr1[i]);
            i++
        } else {
            arr.push(arr2[j]);
            j++
        }
    }
    return arr;
}

Upvotes: 0

Darkpiece
Darkpiece

Reputation: 111

Shortest Merge Sorted arrays without sort() plus, without using third temp array.

function mergeSortedArray (a, b){
  let index = 0;

  while(b.length > 0 && a[index]) {
    if(a[index] > b[0]) {
      a.splice(index, 0, b.shift());
    }
    index++;
  }
  return [...a, ...b];
}
mergeSortedArray([1,2,3,5,9],[4,6,7,8])

Upvotes: 1

l1b3rty
l1b3rty

Reputation: 3642

I needed it so implemented my ownn

mergesortedarray(a, b) {
  let c = new Array(a.length+b.length);
  for(let i=0, j=0, k=0; i<c.length; i++)
    c[i] = j < a.length && (k == b.length || a[j] < b[k]) ? a[j++] : b[k++];
}

Upvotes: 1

akshay bagade
akshay bagade

Reputation: 1219

can do with es6 spread operator

let a=[1,2,3,5,9]
let b=[4,6,7,8]

let newArray=[...a,...b].sort()
console.log(newArray)

Upvotes: 1

Max Leizerovich
Max Leizerovich

Reputation: 1703

The issue I see with most solutions here is that they don't precreate the array, just pushing into an array when you know the end game size is a little bit wasteful.

This is my suggestion, we can make it a little more efficient but it will make it less readable:

function mergeSortedArrays(arr1, arr2) {
		let i1 = 0, i2 = 0;
		return [...arr1, ...arr2].map(
			() =>
				i1 === arr1.length ? arr2[i2++] :
				i2 === arr2.length ? arr1[i1++] :
				arr1[i1] < arr2[i2]? arr1[i1++] :
				arr2[i2++]
		);
}

console.log(mergeSortedArrays([1,2,3,5,9],[4,6,7,8]))

Upvotes: 0

Kristian MT
Kristian MT

Reputation: 165

Merging two sorted arrays.

function merge(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let k = i + j + 1; //(a.length + b.length - 1) == (i + j + 2 - 1) == (i + j + 1)

  while (k >= 0) {
    if (a[i] > b[j] || j < 0) {
      a[k] = a[i];
      i--;
    } else {
      a[k] = b[j];
      j--;
    }
    k--;
  }
  return a;
}

console.log(merge([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21], [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]));

More compact code:

function merge(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let k = i + j + 1; //(a.length + b.length - 1) == (i + j + 2 - 1) == (i + j + 1)

  while (k >= 0) {
    a[k--] = (a[i] > b[j] || j < 0) ? a[i--] : b[j--];
  }
  return a;
}

console.log(merge([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21], [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]));

Upvotes: 0

user6184932
user6184932

Reputation:

Merge two sorted arrays - Answer with comments

const mergeArrays = (arr1, arr2) => { // function to merge two sorted arrays
  if (!arr1 || !arr2) { // if only one array is passed
    return "Invalid Array" // message is returned
  }
  if (arr1.length < 1) { // if first array is empty
    if (arr2.length < 1) { // if second array is empty
      return "Both arrays are empty" // returns message
    }
    return arr2; // else returns second array
  }
  if (arr2.length < 1) { // if second array is empty
    if (arr1.length < 1) { // if both arrays are empty
      return "Both arrays are empty" // returns message
    }
    return arr1; // else returns first array
  }
  let small = []; // initializes empty array to store the smaller array
  let large = []; // initializes empty array to store the larger array
  arr1.length < arr2.length ? [small, large] = [arr1, arr2] : [small, large] = [arr2, arr1]; // stores smaller array in small and larger array in large
  const len1 = small.length; // stores length of small in len1
  const len2 = large.length; // stores length of large in len2
  let ansArr = []; // initializes an empty array to create the merged array
  let i = 0; // initializes i to 0 to iterate through small
  let j = 0; // initializes j to 0 to iterate through large
  while (small[i]!==undefined && large[j]!==undefined) { //while element in arrays at i and j position respectively exists
    if(small[i] < large[j]) { // if element from small is smaller than element in large
      ansArr.push(small[i]); // add that element to answer
      i++; // move to the next element
    } else { // if element from large is smaller than element in small
      ansArr.push(large[j]); // add that element to answer
      j++; // move to the next element
    }
  }
  if (i < len1) { // if i has not reached the end of array
    ansArr = [...ansArr, ...small.splice(i)]; // add the rest of the elements at the end of the answer
  } else { // if j has not reached the end of array
    ansArr = [...ansArr, ...large.splice(j)]; // add the rest of the elements at the end of the answer
  }
  return ansArr; // return answer
}

console.log(mergeArrays([0,1,5], [2,3,4,6,7,8,9])); // example

Upvotes: 0

Ashok R
Ashok R

Reputation: 20766

Merge two arrays and create new array.

function merge_two_sorted_arrays(arr1, arr2) {
        let i = 0;
        let j = 0;
        let result = [];
        while(i < arr1.length && j < arr2.length) {
            if(arr1[i] <= arr2[j]) {
                result.push(arr1[i]);
                i++;
            } else {
                result.push(arr2[j]);
                j++;
            }
        }
        while(i < arr1.length ) {
            result.push(arr1[i]);
            i++;
        }
        while(j < arr2.length ) {
            result.push(arr2[j]);
            j++;
        }
        console.log(result);
    }

merge_two_sorted_arrays([15, 24, 36, 37, 88], [3, 4, 10, 11, 13, 20]);

Upvotes: 0

David Lac
David Lac

Reputation: 95

Hey I ran everyone's code from above against a simple .concat() and .sort() method. With both large and small arrays, the .concat() and .sort() completes in less time, significantly.

console.time("mergeArrays");
mergeArrays([1,2,3,5,9],[4,6,7,8])
console.timeEnd("mergeArrays");
//mergeArrays: 0.299ms

console.time("concat sort");
[1,2,3,5,9].concat([4,6,7,8]).sort();
console.timeEnd("concat sort");
//concat sort:0.018ms

With arrays of 10,000 size, the difference is even larger with the concat and sort running even faster than before (4.831 ms vs .008 ms).

What's happening in javascript's sort that makes it faster?

Upvotes: 7

pranabesh chand
pranabesh chand

Reputation: 91

If you don't care about performance of the sort operation, you can use Array.sort:

var a=[1,2,3,5,9];
var b=[4,6,7,8];
var c = a.concat(b).sort((a,b)=>a > b);
console.log(c)

Of course, using the knowledge that the two arrays are already sorted can reduce runtime.

Upvotes: 0

James Harrison
James Harrison

Reputation: 1031

function mergeArrays(arr1, arr2) {

    if (!arePopulatedArrays(arr1, arr2))
        return getInvalidArraysResult(arr1, arr2);

    let arr1Index = 0;
    let arr2Index = 0;
    const totalItems = arr1.length + arr2.length;
    const mergedArray = new Array(totalItems);

    for (let i = 0; i < totalItems; i++) {

        if (hasItems(arr1, arr1Index)) {

            if (hasItems(arr2, arr2Index)) {

                if (HasSmallestItem(arr1, arr2, arr1Index, arr2Index)) {
                    mergedArray[i] = arr1[arr1Index++];
                } else {
                    mergedArray[i] = arr2[arr2Index++];
                }
            } else {
                mergedArray[i] = arr1[arr1Index++];
            }
        } else {
            mergedArray[i] = arr2[arr2Index++];
        }
    }
    return mergedArray;
}

function arePopulatedArrays(arr1, arr2) {

    if (!arr1 || arr1.length === 0)
        return false;

    if (!arr2 || arr2.length === 0)
        return false;

    return true;
}

function getInvalidArraysResult(arr1, arr2) {

    if (!arr1 && !arr2)
        return [];

    if ((!arr2 || arr2.length === 0) && (arr1 && arr1.length !== 0))
        return arr1;

    if ((!arr1 || arr1.length === 0) && (arr2 && arr2.length !== 0))
        return arr2;

    return [];
}

function hasItems(arr, index) {
    return index < arr.length;
}

function HasSmallestItem(arr1, arr2, arr1Index, arr2Index) {
    return arr1[arr1Index] <= arr2[arr2Index];
}

Upvotes: 0

Lior Elrom
Lior Elrom

Reputation: 20862

Merge Two Sorted Arrays

function merge(arr1, arr2) {
    const arr = [];

    while (arr1.length && arr2.length) {
        if (arr1[0] < arr2[0]) {
            arr.push(arr1.shift());
        } else {
            arr.push(arr2.shift());
        }
    }
    return [...arr, ...arr1, ...arr2];
}

* If you want to merge the arrays in-place, clone each array and use it in the while loop instead.

Example: clonedArr1 = [...arr1];

Upvotes: 0

Related Questions