1. A video encoding device comprising an inter predictor configured to perform merge encoding processing on prediction units in a predetermined order, the prediction units being obtained by dividing a picture of a video, wherein the inter predictor includes an evaluation-order determination part configured to determine merge candidates for a current prediction unit, which is a processing target, and an order of evaluation of the merge candidates, a merge-candidate derivation part configured to sequentially evaluate the merge candidates and calculate costs of the merge candidates in the order of evaluation, a merge-candidate determination part configured to output a merge index corresponding to a position of the merge candidate with the smallest cost among the costs calculated by the merge-candidate derivation part, and a merge encoder configured to encode the merge index with a predetermined encoding scheme, and before completion of the merge encoding processing of a prediction unit immediately preceding the current prediction unit, the evaluation-order determination part determines a first order of evaluation with the immediately preceding prediction unit excluded from the merge candidates to be evaluated and, after the completion of the merge encoding processing of the immediately preceding prediction unit, the evaluation-order determination part determines a second order of evaluation with the immediately preceding prediction unit included in the merge candidates to be evaluated.