A sound segment sorting unit (103) sorts the sound segments of a video. An image segment sorting unit (104) sorts the image segments of the video. A multiple sorting result generation unit (105) generates a plurality of sound segment sorting results and/or a plurality of image segment sorting results. A sorting result pair generation unit (106) generates a plurality of sorting result pairs of the sorting results as the candidates of the optimum segment sorting result of the video. A sorting result output unit (108) compares the sorting result comparative scores of the sorting result pairs calculated by a sorting result comparative score calculation unit (107) and thus outputs a sound segment sorting result and an image segment sorting result having good correspondence. This allows to accurately sort, for each object, a plurality of sound segments and a plurality of image segments contained in the video without adjusting parameters in advance.