8.2.1 reduce sorting to convex hull

Definition: A sequence of points S_i = (x_i, y_i), for i = 1 to k is a convex polygon (in counterclockwise order) if, in the sequence T of size k+2 consisting S₁, ..., S_k, S₁, S₂, each adjacent triple of points T_i, T_i+1, T_i+2 represents a a left turn, for i = 1 to k. The convex hull of a point set P is a subset S of P such that S is a convex polygon and every point of P-S is interior to S.

Problem Convex Hull(S)
Input: S is a sequence of points (x_i,y_i) in the plane.
Output: permute S and return k such that S₁, ... S_k is the convex hull of S.

The reduction of Sorting problem to Convex Hull problem:
Reduction sortByConvexHull(S){// S is a sequence of numbers.

1. for i in 1..n, set P[i] = point(S[i], S[i]²); /* in other words, set P = { (x, x²) | x in S } */
2. k = convexHull(P); /* We know in advance that k will be size(P).*/
3. for i in 1..n, set S[i] = P[i].first; /* first = the x of a (x, x²) pair. */