how to indicate Infinity as sentinel card in mergeSort?

Question

I am reading introduction to algorithms,there is a term "sentinel card" that use ∞ as the sentinel value at P31. I know it means array at the end (and for strings, can use a NULL pointer indicate at the end of strings). But I don't know how to exactly implement in c programming.

Assume that a int array int A[6] have some random value that must include -2147483648(INT_MIN), 0 and 2147483647(INT_MAX).

INT_MIN and INT_MAX at /usr/include/limits.h on Linux platform.

For example:

int A[6] = {100,0,-2147483648, -100, 2147483646 ,2147483647};

so how to indicate ∞ as the sentinel value in c programming at following pseudocode(line 8 and 9)?

MERGE (A ,p ,q, r)
 1    n1 = q - p + 1
 2    n2 = r - q
 3    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4    for i = 1 to n1
 5        L[i] = A[p + i - 1]
 6    for j = 1 to n2
 7        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        if L[i] <= R[j]
14            A[k] = L[i]
15            i = i + 1
16        else A[k] = R[j]
17            j = j + 1

Yosoku Denkai Yosoku Denkai · Accepted Answer · 2019-05-01T04:42:31

One answer would be that ∞ is a number which is larger than your arrays Max by 1 and -∞ is a number that is smaller than your arrays min by 1.And you can make a check each time before calling MERGE for what those values are

how to indicate Infinity as sentinel card in mergeSort?

1 Answers