Skip to main content

Posts

Showing posts from May, 2015

Merging sorted collections

Recently I had a chance to implement an interesting optimization for combining two sorted sets into another sorted set in JavaScript (by "sets" I mean arrays with unique elements). Additional requirement for the algorithm was that when matches are found in two sets, element from the first set should always appear in the result.

The general approach of the implementation is the one used by SQL Server in its Merge physical join operator - since arrays are already sorted, both of them need to be iterated only once and there is no need for hashes to avoid duplicates. This approach would work even better with linked lists, since source items could be added directly into target efficiently without the need to create a separate array object.

This is one of those algorithms, which is so simple but so efficient at the same time, so it is a great pleasure to implement. Resulting gist is presented below: