Technique: Sentinels

A sentinel is an extra item added to one end of an array (or list) to ensure that a loop will terminate without having to include a separate check as in the algorithm:

 SEQUENTIAL_SEARCH: procedure expose A. parse arg N, V Np1 = N + 1; A.Np1 = V do J = 1 until A.J = V; end return J

It is elegant and a bit faster than the following solution. For N=15000, it averages about 20% faster, but it is the difference between 0.28 and 0.22 seconds.

 SEQUENTIAL_SEARCH_WITHOUT_SENTINEL: procedure expose A. parse arg N, V do J = 1 to N   if A.J = V then leave end return J

Now suppose that we have two sorted arrays (in ascending order) A.1,...,A.M and B.1,...,B.N of integers which we wish to merge into a third C. array of M+N elements. Using sentinels provides a way to write a very simple algorithm (compare with merging without sentinel: SPARSE_POLYADD).

 MERGING: procedure expose A. B. C. parse arg M, N Mp1 = M + 1; Np1 = N + 1 if A.M > B.N   then B.Np1 = A.M   else A.Mp1 = B.N K = 1; L = 1 do J = 1 to N + M   if A.K < B.L     then do       C.J = A.K; K = K + 1     end     else do       C.J = B.L; L = L + 1     end end return

A FEW OTHER EXAMPLES

Literature
Kruse R. L. Data Structures and Program Design
Prentice Hall International Editions, ISBN 0-13-196049-0.
Sedgewick R., Algorithms