VietMX Staff asked 3 years ago
Let’s look at the merge principle:
Given two separate lists A and B ordered from least to greatest, construct a list C by:
- repeatedly comparing the least value of A to the least value of B,
- removing (or moving a pointer) the lesser value, and appending it onto C.
- when one list is exhausted, append the remaining items in the other list onto C in order.
- The list C is then also a sorted list.
Complexity Analysis
This problem will have O(n) complexity at best.
Implementation
function merge(a, b) {
var result = [];
var ai = 0;
var bi = 0;
while (true) {
if (ai < a.length && bi < b.length) {
if (a[ai] < b[bi]) {
result.push(a[ai]);
ai++;
} else if (a[ai] > b[bi]) {
result.push(b[bi]);
bi++;
} else {
result.push(a[ai]);
result.push(b[bi]);
ai++;
bi++;
}
} else if (ai < a.length) {
result.push.apply(result, a.slice(ai, a.length));
break;
} else if (bi < b.length) {
result.push.apply(result, b.slice(bi, b.length));
break;
} else {
break;
}
}
return result;
}
