Im looking at some pseudo code. The following snippet (straight off of wiki). It initializes a sort using an array passed into the sorting method ( as m ). Im not to clear on what else statement is saying:

 middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)

4/20/2006 6:44:12 PM

it simply splits the array in "half" and calls mergesort with each half.

[Edited on April 20, 2006 at 10:41 PM. Reason : .]

4/20/2006 10:40:40 PM

Seems to me that the first half of the array elements are added to the variable "left" then the second half are added to "right", then the resulting variables are passed to the mergesort method and the return is written back to those variables.

4/20/2006 11:43:16 PM

Now you can't do it like this

public class MergeSort extends Sort {
	
	int[] scratch;
	
	public MergeSort(boolean trace)
	{
	}
		
	public int[] sort ()
	{
		scratch = new int[data.length];
		
		mergesort( data, 0, data.length - 1);

		return data;
	}
	
	private void mergesort( int[] list, int left, int right )
	{
		if( right <= left )
		{
			return;
		}
		
		int middle = (right+left)/2;
		
		mergesort(list, left, middle);
		mergesort(list, middle + 1, right);

		merge(list, left, middle , right);		
	}
	
	private void merge( int[] list, int left, int middle, int right)
	{		
		for( int i = left; i < right + 1; i++)
		{
			scratch[ i ] = list[ i ];
		}
		
		int leftCursor = left;
		int rightCursor = middle + 1;
		int mainCursor = left;
		
		while( leftCursor < middle + 1 && rightCursor < right + 1)
		{			
			if( scratch[ rightCursor ] < scratch[ leftCursor ])
			{
				list[ mainCursor ] = scratch[ rightCursor ];
				rightCursor++;
			}
			else
			{
				list[ mainCursor ] = scratch[ leftCursor ];
				leftCursor++;
			}
						
			mainCursor++;
		}
		

		while( leftCursor < middle + 1)
		{			
			list[ mainCursor ] = scratch[ leftCursor ];
			leftCursor++;
			
			mainCursor++;
		}
		
		while( rightCursor < right + 1 )
		{
			list[ mainCursor ] = scratch[ rightCursor ];
			rightCursor++;
			
			mainCursor++;
		}
	}
}

4/20/2006 11:55:18 PM