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

Wisp

This is not a c code ??. – Aundreaaunson

this is just the algorithm... a pseudo code – Wisp

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).

Variole

Null-terminated strings are also a perfect example. – Stannite

so why do we have used it here... please explain. And what should i write in place of infinity in my c code? – Wisp

I've tried to explain. If you're writing in C you could just use a very big number to represent the sentinel :) – Variole

You can use INT_MAX from limits.h to get the biggest number. – Loose

hey jeff, pls explain the last line u said... how it helps to make "handling" simplified?? whats handling? – Wisp

All I meant is that the comparison between an integer and infinity is simple (infinity is greater than everything!). That's why it makes a good sentinel for merge-sort. – Variole

Yeah i got that. But my question is that why do we use the array L and R of size n+1 and add infinity at the last. Whats the need of that? Does it makes the algorithm better?? if yes, how? – Wisp

Without a sentinel, you will need explicit code to detect and handle the end of the lists. The sentinel removes the need for these checks, and thereby (arguably) makes the implementation simpler. – Paulettepauley

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.

Fulgurating

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.

Goebel