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 value of the component type of [math]\displaystyle{ S }[/math].

Output

A permutation of [math]\displaystyle{ S }[/math] and [math]\displaystyle{ m_1,\,m_2\in\{1,\ldots,n+1\} }[/math] such that [math]\displaystyle{ m_1\le m_2 }[/math] and

1. [math]\displaystyle{ S[i]\lt p }[/math] for [math]\displaystyle{ i\in\{1,\ldots,m_1-1\} }[/math];
2. [math]\displaystyle{ S[i]=p }[/math] for [math]\displaystyle{ i\in\{m_11,\ldots,m_2-1\} }[/math];
3. [math]\displaystyle{ S[i]\gt p }[/math] for [math]\displaystyle{ i\in\{m_2,\ldots,n\} }[/math].

Objective

N/A

Complexity

Polynomial.

Known algorithms

1. Pivot partitioning by scanning