What is a C guardian? I studied Merge sorting and stumbled using a sentinel signal as infinity at the merge stage

Question

I studied Merge sorting and came across using a sentinel signal as infinity in the merge step.

Here is the algorithm from Cormen's book. Why did we use infinity in steps 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 sensor is a dummy value used to distinguish between values ​​that should be there (for example, user input) and control values ​​(values ​​that need to be specially processed). A simple example of one would be to use zero to zero to mark the end of the list.

In this particular case, the use of infinity simplifies the comparison logic when two halves of the list are combined together (for example, when merging something compared to infinity, there will be less, so processing the end of the merge is simplified).

Answer 2

A checksum value is simply a value that cannot be valid.

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

If my domain is limited to positive numbers, for which I would use an unsigned integer, I can use a signed integer and a negative number as a control. (Of course, I'm losing the upper half of the range unsigned for this.)

If I use a pointer to indicate a value, a null pointer can be a sentinel.

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

A watch signal is simply a value that your actual inputs can never be accepted. Since it cannot be mistaken for a valid value, your code can do “something special” when it sees a sentinel value, something other than the normal processing that it does for a valid value.

Answer 3

In this case, adding infinity (more than any number) to the end of each auxiliary array at each stage of the recursion will avoid additional comparisons in the following cases when combining two auxiliary arrays

• When the first array is completed and the second array remains
• Or when the second array is complete and the first array remains

there is no need to write additional logic in both cases to check if any of the array is complete or not if you finish writing additional code.