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:

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

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]));

Answers:

Answer

Based on Eric Lundgren's answer above, but this fixes a couple of major bugs and is more efficient. Worked for me in production. I included using a sort function for more complex solutions - for this simple case you can just test for a > b as in Eric's answer if you want.

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

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

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

    return sorted;
}

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

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

How about something like this?

Since a and b are both sorted we only need to consider the top or first item of each array when adding. Note that this method will modify both a and b during execution, this may not be what you want, in which case you can add this code at the start:

var tempA = a.slice();
var tembB = b.slice();

This will make copies of the array which you can then use instead of a and b in the function below:

function mergeSortedArray(a,b){
    var tempArray = [];
    while(a.length || b.length) {
        if(typeof a[0] === 'undefined') {
            tempArray.push(b[0]);
            b.splice(0,1);
        } else if(a[0] > b[0]){
            tempArray.push(b[0]);
            b.splice(0,1);
        } else {
            tempArray.push(a[0]);
            a.splice(0,1);
        }
    }
    return tempArray;
}
console.log(mergeSortedArray([4,6,7,8], [1,2,3,5,9]));

Without using splice at all, try something like this:

function mergeSortedArray(a,b){
    var tempArray = [];
    var currentPos = {
        a: 0,
        b: 0
    }
    while(currentPos.a < a.length || currentPos.b < b.length) {
        if(typeof a[currentPos.a] === 'undefined') {
            tempArray.push(b[currentPos.b++]);
        } else if(a[currentPos.a] > b[currentPos.b]){
            tempArray.push(b[currentPos.b++]);
        } else {
            tempArray.push(a[currentPos.a++]);
        }
    }
    return tempArray;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));

Answer

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?

Answer

function mergeSortedArray(a, b) {
    var arr = a.concat(b).sort(function(a, b) {
        return a - b;
     });
    return arr;
 }
 console.log(mergeSortedArray(a, b));

Answer

I wanted to add a solution that included an array with an initialized size, so that there are no copies of the arrays made outside of the new sorted array. This means no calls to slice or extra concat:

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

function mergeSortedArray(arrA, arrB, comparator) {
    var _comparator = (typeof comparator === 'undefined')
        ? defaultComparator
        : comparator;
    var idxA = 0, idxB = 0, idxS = 0;
    var arrSorted = new Array(arrA.length + arrB.length);
    while (idxA < arrA.length || idxB < arrB.length) {
        if (idxA >= arrA.length)
            arrSorted[idxS++] = arrB[idxB++];
        else if (idxB >= arrB.length)
            arrSorted[idxS++] = arrA[idxA++];
        else if (_comparator(arrA[idxA], arrB[idxB]) <= 0)
            arrSorted[idxS++] = arrA[idxA++];
        else
            arrSorted[idxS++] = arrB[idxB++];
    }
    return arrSorted;
}

console.log(mergeSortedArray([0,2,3,5,9],[-3,1,5,6,9.5]));
console.log(mergeSortedArray(
    [{ n: 0 }, { n: 2 }, { n: 3 }, { n: 5 }, { n: 9 }],
    [{ n: -2 }, { n: 0 }, { n: 4 }],
    function(a, b) { return a.n - b.n; }
))

Answer

Lets implement a generic merger. Assuming that we don't know whether they are sorted ascending or descending we first need to apply a test to derive a compare function cf. Then it's a simple recursive walk as follows;

function merger(a, b){
  var cf = a[0] < a[1] || b[0] < b[1] ? (x,y) => x < y
                                      : a[0] > a[1] || b[0] > b[1] ? (x,y) => x > y
                                                                   : (x,y) => false,
      mg = ([a,...as],[b,...bs]) => a !== void 0 &&
                                    b !== void 0  ? cf(a,b) ? [a].concat(mg(as,[b,...bs]))
                                                            : [b].concat(mg([a,...as],bs))
                                                  : a === void 0 ? [b,...bs]
                                                                 : [a,...as];
  return mg(a,b);
}

var a = [1,2,3,5,9,10,11,12],
    b = [4,6,7,8,17],
    c = [9,8,7],
    d = [23,11,10,4,3,2,1];

console.log(merger(a,b));
console.log(merger(c,d));

Note: The tester to decide whether ascending or descending is sloppy. It doesn't even check equity of first two. It's just to give an idea. Implementing it properly is beyond the scope of this question.

Answer

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];

Answer
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];
}
Answer

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.

Answer

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]);

Answer

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
Answer

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]));

Answer

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]))

Answer

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)

Answer

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++];
}
Answer

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])
Answer

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;
}
Answer

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]));

Answer
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)
Answer
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.

Answer

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 ]));

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.