A permutation apparatus , where C is a cache size of the permutation apparatus , X is a unit to store, D is a predetermined number of segmentations, E is a recursion depth, a^ is a vector of length m, b → is a sequence of values less than D representing allocation destinations in a buffer, x → is a sequence of values representing permutation destinations within the respective allocation destinations, d → is a vector representing a buffer of length m, i is each integer equal to or greater than 0 and less than D, j is each integer equal to or greater than 0 and less than m, S i is a start position corresponding to an i-th allocation destination, and N i is the number of elements to be contained in the i-th allocation destination, the permutation apparatus comprising an initial position setting unit , a rearrangement unit , and a permutation execution unit , characterized in that the data size of m pieces of data is assumed to be greater than C; D is a value of about C/X; the data size of m/D E is a magnitude that fits in the cache; the initial position setting unit is adapted to set, for each integer i, the start position S i into a value P i indicating a position within processing corresponding to the i-th allocation destination; the rearrangement unit is adapted to set, for each integer j, a j-th element a j of the vector a → into a P b_j -th element d P_b_j in the buffer d → ; the permutation execution unit is adapted to generate, for each integer i, N i elements c S-i , ..., c S_i+N_i-1 starting at an Si-th element of an output vector c^ by executing an arbitrary inverse permutation algorithm on N i elements d S_i , ..., d S_i+N_i-1 starting at an Si-th element in the buffer d → using N i elements starting at an Si-th element of the sequence x^; and when E ≥ 2, the processing of the permutation apparatus is recursively executed. where C is a cache size of the permutation apparatus , X is a unit to store, D is a predetermined number of segmentations, E is a recursion depth, a^ is a vector of length m, b → is a sequence of values less than D representing allocation destinations in a buffer, x → is a sequence of values representing permutation destinations within the respective allocation destinations, d → is a vector representing a buffer of length m, i is each integer equal to or greater than 0 and less than D, j is each integer equal to or greater than 0 and less than m, S i is a start position corresponding to an i-th allocation destination, and N i is the number of elements to be contained in the i-th allocation destination, the permutation apparatus comprising an initial position setting unit , a rearrangement unit , and a permutation execution unit , characterized in that the data size of m pieces of data is assumed to be greater than C; D is a value of about C/X; the data size of m/D E is a magnitude that fits in the cache; the initial position setting unit is adapted to set, for each integer i, the start position S i into a value P i indicating a position within processing corresponding to the i-th allocation destination; the rearrangement unit is adapted to set, for each integer j, a j-th element a j of the vector a → into a P b_j -th element d P_b_j in the buffer d → ; the permutation execution unit is adapted to generate, for each integer i, N i elements c S-i , ..., c S_i+N_i-1 starting at an Si-th element of an output vector c^ by executing an arbitrary inverse permutation algorithm on N i elements d S_i , ..., d S_i+N_i-1 starting at an Si-th element in the buffer d → using N i elements starting at an Si-th element of the sequence x^; and when E ≥ 2, the processing of the permutation apparatus is recursively executed. <EOS>