Pivot partioning

Input

1. An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math].
2. A definition of comparison on the component type of [math]\displaystyle{ S }[/math].
3. A pivot valiue of the component type of [math]\displaystyle{ S }[/math].

Output

A permutation of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ S[i] \le S[i+1] }[/math] for all [math]\displaystyle{ i\in \{1,...,n-1\} }[/math].

Objective

N/A

Complexity

Polynomial.

Known algorithms

1. Pivot partitioning by scanning