A confidential sort system comprising first, second, ..., and Mth apparatuses, wherein assuming that a body of data to be sorted is a value → v, a tag that determines order after the sort is a key, a bit length of the key is L', N is a predetermined positive integer, an (n+1)th (n=0,..., N-1) bit string when the key is divided into N bit strings is → k n , wherein when an arbitrary value or permutation is assumed as x A , {x A } is a replicated share of x A , and when an arbitrary value is assumed as x A , [[x A ]] is a share of x A having homomorphism, and further assuming that M is a predetermined positive integer of 2 or more, ρ , π are permutations, and a hybrid permutation of π is {{π}} = ({ρ}, ρ -1 π), the first, second, ..., and Mth apparatuses obtain inverse permutation [[σ 0 -1 ]] of stable sort of { → k 0 } from input { → k 0 }, the first, second, ..., and Mth apparatuses perform, on i=1,..., N-1: a process of obtaining {{σ i-1 -1 }} by converting [[σ i-1 -1 ]] to hybrid permutation; a process of obtaining {σ i-1 → k i } by inversely permutating { → k i using {{σ i-1 -1 }}; a process of obtaining inverse permutation [[σ i '-1 ]] of stable sort of [[σ i-1 → k i ]]; a process of obtaining [[σ i -1 ]]:=[[σ i-1 -1 σ i '-1 ]] by synthesizing {{σ i-1 -1 }} with [[σ i '-1 ]]; and a process of obtaining {{σ N-1 -1 }} by converting [[σ N-1 -1 11 to hybrid permutation, and the first, second, ..., and Mth apparatuses output [[σ N-1 → v]] by inversely permutating [[ → v]] using {{σ N-1 -1 }}. assuming that a body of data to be sorted is a value → v, a tag that determines order after the sort is a key, a bit length of the key is L', N is a predetermined positive integer, an (n+1)th (n=0,..., N-1) bit string when the key is divided into N bit strings is → k n , wherein when an arbitrary value or permutation is assumed as x A , {x A } is a replicated share of x A , and when an arbitrary value is assumed as x A , [[x A ]] is a share of x A having homomorphism, and further assuming that M is a predetermined positive integer of 2 or more, ρ , π are permutations, and a hybrid permutation of π is {{π}} = ({ρ}, ρ -1 π), the first, second, ..., and Mth apparatuses obtain inverse permutation [[σ 0 -1 ]] of stable sort of { → k 0 } from input { → k 0 }, the first, second, ..., and Mth apparatuses perform, on i=1,..., N-1: a process of obtaining {{σ i-1 -1 }} by converting [[σ i-1 -1 ]] to hybrid permutation; a process of obtaining {σ i-1 → k i } by inversely permutating { → k i using {{σ i-1 -1 }}; a process of obtaining inverse permutation [[σ i '-1 ]] of stable sort of [[σ i-1 → k i ]]; a process of obtaining [[σ i -1 ]]:=[[σ i-1 -1 σ i '-1 ]] by synthesizing {{σ i-1 -1 }} with [[σ i '-1 ]]; and a process of obtaining {{σ N-1 -1 }} by converting [[σ N-1 -1 11 to hybrid permutation, and the first, second, ..., and Mth apparatuses output [[σ N-1 → v]] by inversely permutating [[ → v]] using {{σ N-1 -1 }}. a process of obtaining {{σ i-1 -1 }} by converting [[σ i-1 -1 ]] to hybrid permutation; a process of obtaining {σ i-1 → k i } by inversely permutating { → k i using {{σ i-1 -1 }}; a process of obtaining inverse permutation [[σ i '-1 ]] of stable sort of [[σ i-1 → k i ]]; a process of obtaining [[σ i -1 ]]:=[[σ i-1 -1 σ i '-1 ]] by synthesizing {{σ i-1 -1 }} with [[σ i '-1 ]]; and a process of obtaining {{σ N-1 -1 }} by converting [[σ N-1 -1 11 to hybrid permutation, and the first, second, ..., and Mth apparatuses output [[σ N-1 → v]] by inversely permutating [[ → v]] using {{σ N-1 -1 }}. <EOS>