Before completion of merge encoding processing of an immediately preceding PU, a controller determines the order of evaluation of merge candidates with the immediately preceding PU excluded from the merge candidates to be evaluated, and a merge-candidate derivation part evaluates each merge candidate in the order of evaluation. After the completion of the merge encoding processing of the immediately preceding PU, the controller re-determines the order of evaluation of merge candidates with the immediately preceding PU included in the merge candidates to be evaluated, and the merge-candidate derivation part evaluates each merge candidate in the re-determined order of evaluation excluding the merge candidate whose evaluation has already been started.