std-merge


Synopsis

(std-merge <lst1> <lst2> <less-pred>)

Description

STD-MERGE returns a union out of two sorted lists, the sort order of the given list must be determined by the less predicate. The result is also sorted.

It is similar to (STD-ORDERED-UNION lst1 lst2) but is faster for since the arguments already must be sorted. The resulting order is determined by looking at the next elements of both lists and take the lower one.

Note

There is also a special function STD-%MERGE-RANDOM which is 5-7% faster on truly random lists, so we support it too, but not in SMALL: #- SMALL

STD-%MERGE-RANDOM is 2 times slower on almost sorted or backwards sorted lists

Examples

(std-merge '(0 2 3) '(1 4 5) '<)	=> (0 1 2 3 4 5)
;; sort order violation:
(std-merge '(2 3 0) '(1 4 5) '<)	=> (1 2 3 0 4 5)

Arguments

lst1, lst2: any proper lists

less-pred: a function or lambda list accepting 2 arguments, and returning nil if the second argument is smaller than the first.

Return Value

A union of the two lists with keeping the sorted order.

Side Effects

The predicate might produce side-effects, but this is generally not a good idea.

Module

(std-require 'STDLIST)

Defined in STDLIST