What are sentinel in C language? I was learning Merge sort and came across using sentinel as infinity in the merge step
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
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).