What are sentinel in C language? I was learning Merge sort and came across using sentinel as infinity in the merge step

Question

I was learning Merge sort and came across using sentinel as infinity in the merge step.

Here is the algorithm from the Cormen's book. Why we have used infinity in step 8 and 9???

MERGE(A, p, q, r)

1 n1 ← q − p + 1

2 n2 ← r − q

3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]

4 for i ← 1 to n1

5 do L[i ] ← A[ p + i − 1]

6 for j ← 1 to n2

7 do R[ j ] ← A[q + j ]

8 L[n1 + 1] ← ∞

9 R[n2 + 1] ← ∞

10 i ← 1

11 j ← 1

12 for k ← p to r

13 do if L[i ] ≤ R[ j ]

14 then A[k] ← L[i ]

15 i ← i + 1

16 else A[k] ← R[ j ]

17 j ← j + 1

Answer 1

A sentinel is a dummy value, used to distinguish between values that are supposed to be there (e.g. user input) and control values (values that need to be handled specially). A simple example of one would be using null to null to mark the end of a list.

In this specific case, the use of infinity simplifies the comparison logic when the two halves of the list are being merged back together (e.g. when merging anything compared to infinity is going to be less, so the handling of the end of the merge is simplified).

Answer 2

A sentinel value is just a value that no valid value could be.

If my domain is limited to positive non-zero numbers, zero can be a sentinel.

If my domain is limited to positive numbers for which I'd otherwise use an unsigned integer, I can use a signed integer and a negative number as a sentinel. (Of course, I lose the upper half of the range of unsigned to do this.)

If I'm using a pointer to point at a value, the null pointer can be a sentinel.

If I'm using a c-string, which is a pointer (or an array that decays to a pointer), I can use the null pointer, or in some cases, point to (char) 0 (the "empty string"), as a sentinel.

A sentinel is just a value that is your valid inputs can never take on. Since it can't be mistaken for a valid value, your code can do "something special" when it sees the sentinel value, something other than the normal processing it would do for a valid value.

Answer 3

In this case Adding infinity(larger than any number) to the end of each sub array in each recursion step, will avoid the extra comparisions in following cases when merging back two sub arrays

• When first array is ended and second array is remaining
• Or when second array is ended and first array is remaining

no need to write extra logic in both cases, to check whether any of the array is ended or not,if ended writing some extra code.