Data sorting apparatus capable of detecting completion of data sorting early and sorting method therefor

A sorting method for sorting n data held in n data holding means into a predetermined order, said method comprising the steps of:

• selecting a group of first pairs of the form (2m+1, 2m+2) m=0, 1, 2, . . . j-1, each pair including predetermined adjacent two data holding means of said n data holding means;
• comparing two data held in the paired two data holding means for each pair selected in said first pair selecting step, to obtain a first comparison, said first comparison means including
• j first comparison circuits each connected between the two data holding means paired by said first pair selecting means, for comparing the two data held within said paired two data holding means;
• exchanging the held data between the paired two data holding means for each pair selected in said first pair selecting step, in response to said first comparison result;
• selecting a group of second pairs of the form (2m+2, 2m+3) m=0, 1, 2, . . . k-1, each pair including predetermined other adjacent two data holding means of said n data holding means which are not selected in said first pair selecting step;
• comparing two data held in the paired two data holding means for each pair selected in said second pair selecting step, said second comparison means including
• k second comparison circuits each connected between the two data holding means paired by said second pair selecting means, for comparing the two data held within said paired two data holding means;
• exchanging the held data between the paired two data holding means for each pair selected in said second pair selecting step;
• and
• detecting completion of sorting of said applied n data in responsive to said first and second comparison result,
• said step of detecting completion including
• detecting a match of the output signals output from said first comparison result,
• detecting a match of the output signals from said second comparison result, and
• detecting a match in response to the result of the first and second detecting a match steps.

A sorting apparatus, comprising:

• sorting means for sorting applied n data into a predetermined order and including
• n data holding means for holding said applied n data,
• first pair selecting means for selecting a group of first pairs of the form (2m+1, 2m+2) m=0, 1, 2, . . . j-1, each pair including predetermined adjacent two data holding means of said n data holding means,
• first comparison means responsive to said first pair selecting means for comparing two data held within the paired two data holding means for each pair selected by said first pair selecting means,
• first data exchange means responsive to said first comparison means for exchanging the held data between the paired two data holding means for each pair selected by said first pair selecting means,
• second pair selecting means for selecting a group of second pairs of the form (2m+2, 2m+3) m=0, 1, 2, . . . k-1, each pair including predetermined other adjacent two data holding means of said n data holding means which are not selected by said first pair selecting means,
• second comparison means responsive to said second pair selecting means for comparing two data held in the paired two data holding means for each pair selected by said second pair selecting means,
• second data exchange means responsive to said second comparison means for exchanging the held data between the paired two data holding means for each pair selected by said second pair selecting means, and
• sorting completion detection means responsive to said first and second comparison means for detecting completion of sorting of said applied n data;
• data dividing means for dividing all data to be sorted into L data groups, each group having said n data or less;
• data applying means for applying the data divided by said dividing means to said sorting means in units of data groups,
• said sorting means sorting the applied data in units of data groups with respect to said L data groups;
• data extracting means for extracting optimum data in said predetermined order from each of said L data groups sorted by said sorting means;
• and
• optimum data determining means for determining optimum data in said predetermined order from the data extracted by said data extracting means.

A sorting apparatus for sorting n data, each data including higher order bit data and lower order bit data, said apparatus comprising:

• n data holding means for holding said n data;
• sorting means for sorting applied data into a predetermined order;
• higher order bit data applying means for applying the respective higher order bit data of said n data to said sorting means, said sorting means carrying out sorting with respect to applied n higher order bit data;
• match data group detecting means for detecting a match data group including matching data from the higher order bit data processed by said sorting means;
• lower order bit data applying means for applying lower order bit data corresponding to the higher order bit data within said match data group to said sorting means, said sorting means carrying out sorting with respect to the applied lower order bit data;
• and
• order determining means for determining the order of said n data in accordance with the result of processing conducted by said sorting means with respect to said higher order bit data and said lower order bit data,
• said sorting means including
• first pair selecting means for selecting a group of first pairs of the form (2m+1, 2m+2) m=0, 1, 2, . . . j-1, each pair including predetermined adjacent two data holding means of said n data holding means,
• first comparison means responsive to said first pair selecting means for comparing two data held within the paired two data holding means for each pair selected by said first pair selecting means, said first comparison means including j first comparison circuits each connected between the two data holding means paired by said first pair selecting means, for comparing the two data held within said paired two data holding means,
• first data exchange means responsive to said first comparison means for exchanging the held data between the paired two data holding means for each pair selected by said first pair selecting means,
• second pair selecting means for selecting a group of second pairs of the form (2m+2, 2m+3) m=0, 1, 2, . . . k-1, each pair including predetermined other adjacent two data holding means of said n data holding means which are not selected by said first pair selecting means,
• second comparison means responsive to said second pair selecting means for comparing two data held in the paired two data holding means for each pair selected by said second pair selecting means, said second comparison means including k second comparison circuits each connected between the two data holding means paired by said second pair selecting means, for comparing the two data held within said paired two data holding means,
• second data exchange means responsive to said second comparison means for exchanging the held data between the paired two data holding means for each pair selected by said second pair selecting means, and
• sorting completion detection means responsive to output signals output form said j first comparison circuits and said k second comparison circuits for detecting completion of sorting of said applied n data,
• said sorting completion detecting means including
• first match detecting means connected to outputs of said j first comparison circuits for detecting a match of the output signals output from said j first comparison circuits,
• second match detecting means connected to outputs of said k second comparison circuits for detecting a match of the output signals from said k second comparison circuits, and
• third match detecting means connected to receive output signals from said first and second match detecting means for detecting match of the output signals from said first and second match detecting means.