Why Does My Java MergeSort Throw IndexOutOfBoundsException with Three Students?

[lypaza]

I wrote a class to sort Comparable elements in a list (ArrayList)
I have Student class that contains lastName, firstName, studentID, and tuitionFee as its instance variables.

At first I used mergeSort algorithm to write the Sorts class. It works when I add 1 student, still works with 2 students, but when I add 3 students, the IndexOutOfBoundsException occurs.

Here is my code:

import java.util.*;


public class Sorts
{
	public static void sort(ArrayList objects)
	{
		mergeSort(objects, 0, (objects.size()-1));
	}

	public static void mergeSort(ArrayList list, int start, int end)
	{
		if (start < end)
		{
			int mid = (int)Math.floor((start + end)/2);
			mergeSort(list, start, mid);
			mergeSort(list, mid+1, end);
			merge(list, start, mid, end);
		}
	}

	public static void merge(ArrayList list, int start, int mid, int end)

	{
		int firstLength = mid - start + 1;
		int secondLength = end - mid;
		Comparable [] first = new Comparable[firstLength];
		Comparable [] second = new Comparable[secondLength];

		for (int i = 0; i < firstLength; i++)
			first[i] = (Comparable)list.get(i);
		for (int i = 0; i < secondLength; i++)
			second[i] = (Comparable)list.get(mid+1+i);

		list.clear();

		int i = 0;
		int j = 0;

		while ((i<firstLength) && (j<secondLength))
		{
			if ( first[i].compareTo(second[j]) < 0)
			{
				list.add(first[i]);
				i++;
			}
			else
			{
				list.add(second[j]);
				j++;
			}
		}

		while (i < firstLength)
		{
			list.add(first[i]);
			i++;
		}

		while (j < secondLength)
		{
			list.add(second[j]);
			j++;
		}

	}

}

I was staring at it without blinking but still don't get it

 

[Valkarie]

Can someone please help me to figure out what's wrong with my code?The problem you have is that you are not adding the elements from the first and second arrays back into the list in the correct order. When you merge two sorted arrays, you should compare the elements at the same index in both arrays and add the one that is smaller to the list. This means that you need to loop through both arrays in parallel and add the elements one by one. Your code is adding all of the elements from the first array before looping through the second array. Instead, you should be looping through both arrays in parallel, comparing and adding each element. You can do this with a while loop like this: while (i < firstLength && j < secondLength) { if (first.compareTo(second[j]) < 0) { list.add(first); i++; } else { list.add(second[j]); j++; }}After the while loop, you should add any remaining elements from either the first or second array. while (i < firstLength) { list.add(first); i++;}while (j < secondLength) { list.add(second[j]); j++;}

 

[piercas]

Hi there,

It seems like you are trying to use a mergeSort algorithm to sort a list of Student objects in your Java program. However, you are running into an IndexOutOfBoundsException when you try to sort a list with three or more students.

First of all, great job on implementing a sorting algorithm in Java! It looks like you have a good understanding of the mergeSort algorithm and how it works. However, there seems to be an issue in your merge method.

In your merge method, you are using a for loop to add elements from the first and second arrays to your list. However, you are using the variable "mid" to access elements from the second array, which may be causing the IndexOutOfBoundsException. Remember, the variable "mid" represents the middle index of the entire list, not just the second array.

To fix this issue, you can change the for loop to start at "mid+1" instead of "0". This will ensure that you are only accessing elements from the second array, and not trying to access elements beyond the size of the array.

I hope this helps and good luck with your sorting algorithm! Keep up the good work!