Help With Mergesort!!!

[johnnyICON]

Hi, I am trying to figure out how to implement a merge sort. I have been at this since 8AM this morning, and its nearing 11PM.

I have gone through every single variation of my code that I could think of, and it has yet to work once. I'm burnt out, can someone help me out?

Here is my Merge method.

public static void mergeSort( int[] arrayToSort, int[] sortedArray, int left, int right )
{
int sizeOfSort = right - left;

// If the sort has more than one element
if ( sizeOfSort > 1 )
{
// Step #1: Find a mid-point
int mid = ( left + right ) / 2;

// Step #2: Recusively sort the left half
mergeSort( arrayToSort, sortedArray, left, mid );

// Step #3: Recursively sort the right half
mergeSort( arrayToSort, sortedArray, mid + 1, right );

// Step #4: Merge the two sub-arrays
int rightStart = mid + 1; // Merging needs to know where the two sub-arrays start
// Left starts at left, right starts at mid + 1

int sortedIndex = left; // A counter exclusively for the sorted array to keep
// track of our current position in sortedArray

while ( left <= mid && rightStart <= right )
{
if ( arrayToSort[ left ] < arrayToSort[ rightStart ] )
sortedArray[ sortedIndex++ ] = arrayToSort[ left++ ];
else
sortedArray[ sortedIndex++ ] = arrayToSort[ rightStart++ ];
}

// Insert any remaining numbers in the left or the right
while ( left <= mid )
sortedArray[ sortedIndex++ ] = arrayToSort[ left++ ];

while ( rightStart <= right )
sortedArray[ sortedIndex++ ] = arrayToSort[ rightStart++ ];
}
}


And here is the mainline
public static void main( String[] args )
{
int[] someArray = { 2, 9,22,33,44, 4,72, 11, 5, 10 };
int[] sortedArray = new int [ someArray.length ];

printArray( someArray );
mergeSort( someArray, sortedArray, 0, someArray.length - 1 );
printArray( sortedArray );
}

The console outputs:
Original 2 9 22 33 44 4 72 11 5 10
Sorted 2 4 9 22 33 44 72 11 5 10

As you can see, the sorted array is NOT sorted. :(

[Bornish]

#1: after sorting the left part and right part separate, the result is in sortedArray, not in arrayToSort, which means your step 4 is wrong because you're using the unsorted halfs when comparing for merging:// this is wrong:
if ( arrayToSort[ left ] < arrayToSort[ rightStart ] )#2: you can choose when to stop sorting, but I think would be easier to sort while your variable sizeOfSort is greater than zero, meaning what your comment was saying: // If the sort has more than one element
if ( sizeOfSort > 0 )#3: when your sort has one element, still you have to copy the element from arrayToSort to sortedArray, so you'll have to add the else branch:if ( sizeOfSort > 0 )
{
//...
}
else
sortedArray[left] = arrayToSort[left];#4: Depending on the language used, not deleting the sorted array would be a memory leak, so, simply consider this as a warning only.
Here's a modified version of your mergeSort() function, which works for your testing dataset, but you should give it a check yourself and even optimize it a bit:public static void mergeSort( int[] arrayToSort, int[] sortedArray, int left, int right )
{
int sizeOfSort = right - left;

// If the sort has more than one element
if ( sizeOfSort > 0 )
{
// Step #1: Find a mid-point
int mid = ( left + right ) / 2;

// Step #2: Recusively sort the left half
mergeSort( arrayToSort, sortedArray, left, mid );

// Step #3: Recursively sort the right half
mergeSort( arrayToSort, sortedArray, mid + 1, right );

// Step #4: Merge the two sub-arrays
int rightStart = mid + 1; // Merging needs to know where the two sub-arrays start
// Left starts at left, right starts at mid + 1

int sortedIndex = left; // A counter exclusively for the sorted array to keep
// track of our current position in sortedArray

int[] tempArray = new int [ sortedArray.length ];
// Bornish: use any method which copies from sortedArray to tempArray
// the "(sizeOfSort+1)" elements starting with index "left"
memcpy(&(tempArray[left]),&(sortedArray[left]),(sizeOfSort + 1)*sizeof(int));
while ( left <= mid && rightStart <= right )
{
if ( tempArray[ left ] < tempArray[ rightStart ] )
sortedArray[ sortedIndex++ ] = tempArray[ left++ ];
else
sortedArray[ sortedIndex++ ] = tempArray[ rightStart++ ];
}

// Insert any remaining numbers in the left or the right
while ( left <= mid )
sortedArray[ sortedIndex++ ] = tempArray[ left++ ];

while ( rightStart <= right )
sortedArray[ sortedIndex++ ] = tempArray[ rightStart++ ];
delete [] tempArray; // Bornish: this is simply a reminder and a warning!
}
else
sortedArray[left] = arrayToSort[left];
}Best regards,

[johnnyICON]

Thanks, I'm still taking a closer a look at what you did.

One thing I should of noted is that the purpose of passing an extra array is exactly
as what you declared as a tempArray. What I was trying to do was point to two
elements in the arrayToSort (A) and compare. The lesser of these two values would
be put into sortedArray (B).

If you look at my posting of my mainline, I declared sortedArray (B) to be the same
size as the arrayToSort (A). By declaring a temporary array, sortedArray (B), outside
of the mergeSort method itself I was hoping to increase its efficiency.

For this particular piece of code I am implementing it with java.

[Bornish]

The classical implementation of merge sort, as I recall it, works best with one and only one linked list, because insertion of elements is possible with no overhead.
If that's possible in your case, it would be faster than copying values.
MergeSort implementation in Java can be found here (http://www.cs.ubc.ca/spider/harrison/Java/MergeSortAlgorithm.java.html) and here (http://www.cs.ubc.ca/spider/harrison/Java/ExtraStorageMergeSortAlgorithm.java.html).
I would recomend for speed to use quickSort also available here (http://www.cs.ubc.ca/spider/harrison/Java/QSortAlgorithm.java.html) and here (http://www.cs.ubc.ca/spider/harrison/Java/FastQSortAlgorithm.java.html).
Good luck,

[johnnyICON]

Awesome, thanks.

Just for clarity though...

The code where you copy the original array into tempArray, could I not copy the original array into the sortedArray, and rather than using the tempArray elements for reference use the original array?


// Copy elements from arrayToSort starting at 0 to sorted array starting at 0 for
// a count of the length of the original array's length.
System.arraycopy( arrayToSort, 0, sortedArray, 0, arrayToSort.length );


Then in the while

if ( arrayToSort[ left ] < arrayToSort[ rightStart ]
...
etc...


that is what I had originally I think, except w/o the copying. I am going to re-read your first post, you may have pointed out my logic error.

[johnnyICON]

#3: when your sort has one element, still you have to copy the element from arrayToSort to sortedArray, so you'll have to add the else branch:if ( sizeOfSort > 0 )
{
//...
}
else
sortedArray[left] = arrayToSort[left];


Did I not accomplish this with the last two while loops?

The first loop will exit prematurely, meaning it will not finish the insertion of all elements from both left and right when the left or right exceeds its reach.

The counters left and rightStart still hold their values from the first while loop, but if their values are less than or equal to mid/right, continuing copying their elements into the sorted array.

[Bornish]

I've already gave you a link containing full source code in Java of a MergeSort using an extra storage:
http://www.cs.ubc.ca/spider/harrison/Java/ExtraStorageMergeSortAlgorithm.java.html
If you'll take a closer look to it's "void sort(int a[], int lo, int hi, int scratch[])", you'll see that is very similar to your function, but the extra array scratch[] is used as temporary, and original array a[] gets modified to the sorted values. That was not what you were doing in your code... and I could not assume that you can modify the original data... and I thought you need the sorted array only in the extra array, because the original array should not be modified.
Forget about my modified version, since the purpose was to have minimum changes to your implementation, but which will point out the logical mistakes you did.
Best regards,