# 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: 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]));
`````` 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 === 'undefined') {
tempArray.push(b);
b.splice(0,1);
} else if(a > b){
tempArray.push(b);
b.splice(0,1);
} else {
tempArray.push(a);
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]));`````` 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? ``````function mergeSortedArray(a, b) {
var arr = a.concat(b).sort(function(a, b) {
return a - b;
});
return arr;
}
console.log(mergeSortedArray(a, b));`````` 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; }
))`````` 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 < a || b < b ? (x,y) => x < y
: a > a || b > b ? (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. # Merge Two Sorted Arrays

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

while (arr1.length && arr2.length) {
if (arr1 < arr2) {
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];` ``````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];
}
`````` 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. 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]);`````` # 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
`````` 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]));`````` 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]))`````` 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)`````` 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++];
}
`````` 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) {
a.splice(index, 0, b.shift());
}
index++;
}
return [...a, ...b];
}
mergeSortedArray([1,2,3,5,9],[4,6,7,8])
`````` 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;
}
`````` 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]));`````` ``````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)
`````` ``````function mergeSortedArray(a, b){
var merged = [],
aElm = a,
bElm = b,
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. 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 ]));``````

## Top Questions

©2020 All rights reserved.