ソート

• マージソート

マージソートのアルゴリズムをC#で実装しています。アルゴリズムの解説は省略します。

ソースの全貌はこちらよりダウンロードしてください。

		
public static SortResult Merge( int[] nDats )
{
	SortResult result = new SortResult( "Merge" );
	result.LogicCompCount = MergeComparison( nDats.Length );
	result.CompCountLogic = "n log2( n )";

	MergeRecursive( nDats, result );

	result.End();
	return result;
}
private static void MergeRecursive( int[] nDats, SortResult result )
{
	if( nDats.Length <= 1 ) return;

	int m = nDats.Length / 2;
	int n = nDats.Length - m;
	int[] a1 = new int[ m ];
	int[] a2 = new int[ n ];

	for( int i = 0; i < m; i++ )
	{
		a1[ i ] = nDats[ i ];
	}

	for( int i = 0; i < n; i++ )
	{
		a2[ i ] = nDats[ m + i ];
	}

	MergeRecursive( a1, result );
	MergeRecursive( a2, result );
	MergeArray( a1, a2, nDats, result );
}

/// <summary>
/// 既にソート済みの2つの配列を併合して新しい配列を生成
/// </summary>
/// <param name="a1">既にソート済みの配列</param>
/// <param name="a2">既にソート済みの配列</param>
/// <param name="nDats">新しい配列</param>
/// <param name="result">ソート結果</param>
private static void MergeArray( int[] a1, int[] a2, int[] nDats, SortResult result )
{
	int i = 0;
	int j = 0;
	while( i < a1.Length || j < a2.Length )
	{
		result.CompCount++;
		if( j >= a2.Length || ( i < a1.Length && a1[ i ] < a2[ j ] ) )
		{
			nDats[ i + j ] = a1[ i ];
			i++;
		}
		else
		{
			nDats[ i + j ] = a2[ j ];
			j++;
		}
	}
}