Javaで分布数え上げソート[CountingSort]（不完全燃焼版）

不完全燃焼と言いつつ乗せたのは、
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A
の問題で、テストケース9以降からメモリだったり実行時間で蹴られてしまったからです。
アルゴリズム的には正しいのですが、もっと効率の良い方法があるのか模索中です。
とは言え、気づいた方、アドバイスいただけるとすごく嬉しいです。
※最後の出力そのもので蹴られている気が。。。

分布数え上げソート

例によって、ソースへ直接コメント書いています。
概念などは下記URLが一番分かりやすかったと思います。
http://www.codereading.com/algo_and_ds/algo/counting_sort.html

要は、サイズや値の範囲が決まっている配列である場合に有効なソート方法であり、
値の発生回数を元に、値の位置を決めていくものです。
速度的には一応ソートアルゴリズムの中で最速とのことです。

コード

CountingSort.java

package aoj.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CountingSort {

    public static void main(String args[]) throws IOException {
        // 入力の受付
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 要素数が入ってくるが、要素数からサイズを取れるので読み捨て
        br.readLine();
        String line = br.readLine();
        // 整数値の配列を取得
        int[] befSort = parseInt(getSplitLine(line));

        /**
         * ここから計数ソート
         */
        // 前提条件
        // 1 ≤ n ≤ 2,000,000 : 要素数
        // 0 ≤ A[i] ≤ 10,000 : 含まれる整数値

        // カウンタ配列（出現回数）の初期化
        // 数値の最大値+1で初期化する
        int maxSize = 2000001;
        int[] counter = new int[maxSize];

        int i;
        for (i = 0; i < befSort.length; i++) {
            // numArrayに含まれる数値の出現回数を計算する
            counter[befSort[i]]++;
            // 2, 5, 1, 3, 2, 3, 0 の配列である場合、
            // counter[0] = 1 回（0）
            // counter[1] = 1 回（1）
            // counter[2] = 2 回（2）
            // counter[3] = 2 回（3）
            // counter[4] = 0 回（4）
            // counter[5] = 1 回（5）
            // の様な計算結果になる
        }
        //
        for (i = 1; i < counter.length; i++) {
            // i 以下の出現回数を計算する
            counter[i] = counter[i] + counter[i - 1];
            // i = 0; counter[i] = 1; 0以下は1つ
            // i = 1; counter[i] = 2; 1以下は2つ
            // i = 2; counter[i] = 4; 2以下は3つ
            // i = 3; counter[i] = 6; 3以下は6つ
            // i = 4; counter[i] = 6; 4以下は6つ
            // i = 5; counter[i] = 7; 5以下は7つ
        }

        // output(ソート結果を登録する配列)へ計算した結果を登録する
        int[] output = new int[maxSize];
        for (i = befSort.length - 1; i >= 0; i--) {
            output[counter[befSort[i]]] = befSort[i];
            // i = 0; output[counter[2]] = 2;
            // i = 0; output[4] = 2;
            // i = 1; output[counter[5]] = 5;
            // i = 1; output[7] = 5;
            // のように、入力配列の出現回数(count[i])の場所へ
            // 数値を登録していくことでソートされる
            counter[befSort[i]]--;
        }

        // 出力
        System.out.print(output[1]);
        for (i = 2; i <= befSort.length; i++) {
            System.out.print(" " + output[i]);
        }
        System.out.println();
    }

    private static String[] getSplitLine(String line) {
        return line.split("\\s");
    }

    private static int[] parseInt(String[] line) {
        int[] numArray = new int[line.length];
        for (int i = 0; i < line.length; i++) {
            numArray[i] = Integer.parseInt(line[i]);
        }
        return numArray;
    }

}