for-loop

variant of the recursive merge

by jpsierens

JavaScript

let steps = 0;

// merges two sorted arrays and sorts them
// complexity: O(n)
// note: input arrays must be sorted
// note: supports arrays with different sizes
const merge = (a, b) => {
  const aCopy = [...a];
  const bCopy = [...b];
  let answer = [];
  
  for (let i = 0; i < a.length; i++) {
  	steps++;
    
    if (aCopy[i] < bCopy[i]) {
    	answer.push(aCopy[i]);
      aCopy.splice(i, 1);
      i--;
    } else {
    	answer.push(bCopy[i]);
      bCopy.splice(i, 1);
      i--;
    }
    
    if (!aCopy.length) {
      answer = [...answer, ...bCopy];
      break;
    } else if (!bCopy.length) {
      answer = [...answer, ...aCopy]
      break;
    }
  }
  
  console.log('steps: '+steps);
  return answer;
}

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