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}}.