マージソート

(KAB-studioからのおしらせです)

// Sample.java
public class Sample
{
    public static void main( String[] args )
    {
        // 出力する配列を用意します。
        int[] ints = new int[]{ 4, 9, 3, 5, 8 };

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 4, 9, 3, 5, 8, 

        // マージソートします。
        mergeSort( ints );

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 3, 4, 5, 8, 9, 
    }

    /**
    *   マージソートします。
    */
    private static void mergeSort( int[] array )
    {
        if( array.length <= 1 )
        {
            // 要素数が１以下なら何もしません。
            return;
        }

        // 中央から左側のサイズを取得します。
        int leftSize = array.length / 2;
        // 中央から右側のサイズを取得します。
        int rightSize = array.length - leftSize;
        // 中央から左側のサイズの配列を作成します。
        int[] leftArray = new int[leftSize];
        // 中央から右側のサイズの配列を作成します。
        int[] rightArray = new int[rightSize];
        // それぞれコピーします。
        int iF1;
        for( iF1 = 0; iF1 < leftSize; ++iF1 )
        {
            leftArray[iF1] = array[iF1];
        }
        
        for( iF1 = 0; iF1 < rightSize; ++iF1 )
        {
            rightArray[iF1] = array[leftSize + iF1];
        }

        // それぞれ再帰呼び出しします。
        mergeSort( leftArray );
        mergeSort( rightArray );

        // マージします。
        int leftPos = 0;
        int rightPos = 0;
        while(
            ( leftPos  < leftSize  ) || 
            ( rightPos < rightSize )
            )
        {
            // 左右両方とも配列の中にいる間、ループします。

            if( rightSize <= rightPos )
            {
                // 右側が配列の最後まで来ている場合。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
            else if( leftSize <= leftPos )
            {
                // 左側が配列の最後まで来ている場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
            }
            else if( leftArray[leftPos] > rightArray[rightPos] )
              {
                // 左側の方が右側より大きい場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
              }
              else
            {
                // それ以外の場合（左側の方が右側より小さい場合）。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
        }
    }
}