When a list to be sorted is divided into L sorted merge objective lists, each of the merge objective lists is formed of a plurality of blocks (where L is any natural number larger than or equal to 2). For each block, a block information record having a block identifier and a key value of a representative record of the block is generated. With the block information records, a first auxiliary information list is generated. The first auxiliary information list is sorted in a predetermined order of key values so as to generate a second auxiliary information list. The second auxiliary information list is almost equally divided into P portions (where P is any natural number larger than or equal to 2). For each of the P sub-auxiliary information lists, a forward boundary value and a backward boundary value are set corresponding to a predetermined rule. The P sub-auxiliary information lists are allocated to P process units. Each of the P process units retrieves a portion (segment) corresponding to the sub-auxiliary information list from the L sorted merge objective lists and merges blocks of the segment.