This invention enables parallelly sorting data in substantially M blocks though statistical information is updated. In the first scan conversion, (15) input transform coefficients of a two-dimensional array are read out and output in accordance with scan order information ScanOrder[ ], thereby outputting sorted one-dimensional array data. At this time, a significant coefficient detection unit determines whether the sorted data is a significant coefficient. Upon receiving a notification that the sorted data is a significant coefficient, a statistical information update unit updates statistical information ScanTotals[x] at a corresponding position. When the relationship between statistical information ScanTotals[x] and immediately preceding statistical information ScanTotals[x−1] is an ascending order, ScanOrder[x−1] and ScanOrder[x], and ScanTotals[x−1] and ScanTotals[x] are swapped respectively. A second scan conversion unit starts scan conversion of transform coefficients with a delay of at least two transform coefficients from a first scan conversion unit.