Thread: Sorting and Merging

public class Merge
{
 
public Merge()
{
 
}
 
public static  int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array
 
int x = A.length + B.length; 
int y = 0; // index of C
 
int[] C = new int[x];
 
 
while ((curr < A.length) && (curr2 < B.length))
{
if A[curr].compareTo(B[curr2] > 0)
{
C[y] = A[curr];
y++;
curr++
 
}
 
else
{
C[y] = B[curr2];
y++;
curr2++;
 
}
}
if (curr == A.length)
{
for (int k = curr2; k < B.length; k++)
{
C[k + curr] = B[curr2];
curr2++;
}
 
 
}
 
else
{
for (int v = curr; v < A.length; v++)
{
C[v + curr2] = A[curr];
curr++;
}
 
}
 
 
return C;
 
}
 
}

Will that always work?

if A[curr].compareTo(B[curr2] > 0)

I think you started getting mixed up a bit here (lack of sleep perhaps?).

public class Merge
{
 
public Merge()
{
 
}
 
public int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array
 
int x = A.length + B.length;
int y = 0; // index of C
String str = "";
int[] C = new int[x];
 
 
while ((curr < A.length) && (curr2 < B.length))
{
if A[curr].compareTo(B[curr2] )> 0)
{
C[y] = A[curr];
y++;
curr++
 
}
 
else
{
C[y] = B[curr2];
y++;
curr2++;
 
}
}
if (curr == A.length)
{
for (int k = curr2; k < B.length; k++)
{
C[k + curr] = B[curr2];
curr2++;
}
 
 
}
 
else
{
for (int v = curr; v < A.length; v++)
{
C[v + curr2] = A[curr];
curr++;
}
 
}
 
 
return C;
 
}
 
public static void inplace_merge(int[] A, int left, int middle, int right)
{
 
int[] sub = new int[(middle-left) + 1];
 
for (int x = 0; x < sub.length; x++)
{
sub[x] = A[x];
}
 
int[] sub2 = new int[right - (middle+1)];
 
for (int y = middle + 1; y < sub2.length; y++)
{
sub2[y] = A[y];
}
 
int[] result = merge(sub, sub2);
int index = 0;
for (int z = left; z <=right; z++)
{
A[z] = result[index];
index++;
}
 
}
 
public static void mergesort(int[] A, int left, int right)
{
if (left>=right)
return;
 
int middle = (left + right) /2;
 
mergesort(A, left, middle);
mergesort(A, middle+1, right);
 
 
inplace_merge(A, left, middle, right);
 
 
 
 
}
 
public static void main(String[] args)
{
Scanner console = new Scanner(System.in);
 
System.out.println("Enter the number of elements in the first array.");
 
int x = console.nextInt();
 
int[] array = new int[x];
 
for (int i =0; i < array.size; i++)
{
System.out.println("Enter the value at index " + i);
array[i] = console.nextInt();
}
 
System.out.println("Enter the number of elements in the second array.");
 
int y = console.nextInt();
 
int[] array2 = new int[y];
 
for (int j =0; j < array2.length; j++)
{
System.out.println("Enter the value at index " + j);
array2[j] = console.nextInt();
}
 
System.out.println("Array 1: " + Arrays.toString(array) + " Array 2: " + Arrays.toString(array2));
 
 
}
 
 
}

Out: 30th November 2010 Type: Medium Due: 8th December 2010 at 11:59pm
Note: You can use Eclipse for this assignment if you wish.
In class we discussed different algorithms to sort an array in ascending order. This assignment explores a useful operation that you can perform on sorted arrays: merging them so that the merged array is also sorted.
Given two arrays A and B of different lengths that are already sorted in ascending order, one can merge them into an array C as follows:
1. Maintain current positions for arrays A and B.
2. If number at current position in A is greater than that in B, add A’s current number to C and advance A’s position. Otherwise add B’s current number to C and advance B’s position.
3. Continue step 2 until you reach the end of one of the two arrays. When you do, copy the remaining elements of the other array to the end of C.
What to do:
1. Write a class Merge. It will have no variables.
2. Write a static method merge in Merge that takes two arrays as parameters and returns the merged array using the above algorithm. Make sure your method works even if there are common numbers in the two arrays, and if one or both arrays have just one number in them. You will not receive any points if you use any other method, including putting numbers in another array and then sorting it.
3. Write another static method inplace_merge in Merge. This method takes a single array A as a parameter, along with three indices left, middle and right. Assuming all three are valid indices, this method assumes that the array A is sorted between (left, middle) and (middle+1, right), including the ends. It then merges these two sub-arrays and copies the result back to A between left and right. You may use the above method to accomplish this if you wish.
4. You have almost implemented a popular algorithm to sort an array, mergesort. The pseudocode for mergesort is as follows: mergesort(A,left,right) { if (left >=right) return Compute middle  floor((left+right)/2) Call mergesort recursively as mergesort(A,left,middle) Call mergesort recursively as mergesort(A,middle+1,right) Merge the two sorted arrays A(left,middle) and A(middle+1,right) in place using inplace_merge above. // Now the array A is sorted correctly from index ‘left’ to index ‘right’. }
Write the above method in the Merge class. Write another method sort(A) that calls the mergesort method so that the array A is sorted.
5. The main method of your program should ask the user for the following input from the keyboard in the given order:
a. Number of elements in 1st array.
b. Numbers of 1st array.
c. Number of elements in 2nd array.
d. Numbers of 2nd array.
It should then print (1) both arrays as entered by the user (2) sorted arrays using the mergesort algorithm (3) the array obtained by merging the two arrays.
Hint: To verify that your merge works correctly, you can use the code from class that sorts arrays using selection, bubble or insertion sort. But make sure that the program you submit uses mergesort to sort the two arrays entered by the user.

Arrays are passed via reference rather than by value, so any changes you make to the object inside another method will be reflected in the original array. This is why your professor had you declare inplace_merge as void (since it doesn't need to return anything).

As a side note, for a true "in-place merge" you can't use a second list and call the original merge to merge these two together Of course, writing an efficient in-place merge requires linked lists and I can see why he has you write that method as it is.

You're algorithm's a bit off, too. Here's the java code that should get you what you want (there are some spots you'll need to fill in still)

public static int[] merge(int[] A, int[] B)
	{
		int aIndex = 0; // current position of first array
		int bIndex = 0; // current position of second array
		int[] result = new int[A.length + B.length];
 
		for(int i = 0; aIndex < A.length || bIndex < B.length; ++i)
		{
			if (aIndex < A.length && bIndex < B.length)
			{
				if (A[aIndex] <= B[bIndex])
				{
					// TODO: something needs to be added to the result array
					// TODO: one of the two indices needs to be increased
				}
				else
				{
					// TODO: something needs to be added to the result array
					// TODO: one of the two indices needs to be increased
				}
			}
			else if (aIndex < A.length)
			{
					// TODO: something needs to be added to the result array
					// TODO: one of the two indices needs to be increased
			}
			else
			{
					// TODO: something needs to be added to the result array
					// TODO: one of the two indices needs to be increased
			}
		}
		return result;
 
	}
 
	public static void inplace_merge(int[] A, int left, int middle, int right)
	{
		int[] leftArray = new int[/*TODO: how long should leftArray be?*/];
		int[] rightArray = new int[/*TODO: how long should rightArray be?*/];
		for (int i = 0; i < leftArray.length; ++i)
		{
			leftArray[i] = A[/*TODO: what index in the original array maps to the left array?*/];
		}
		for (int i = 0; i < rightArray.length; ++i)
		{
			rightArray[i] = A[/*TODO: what index in the original array maps to the right array?*/];
		}
		int[] merged = merge(leftArray, rightArray);
		for (int i = 0; i < merged.length; ++i)
		{
			A[/*TODO: what index in the merged array maps to the original array?*/] = merged[i];
		}
	}

Hmm, are you sorting in ascending order or descending order? Though I guess that doesn't really matter.

The only thing I can see that's wrong is this section:

else if (curr < A.length)
    {
        for (int var = curr ; var < A.length; var++)
        {
            int temp3 = A[var];
            C[i] = temp3;
        }
    }
    else
    {
        for (int var2 = curr2; var2 < B.length; var2++)
        {
            int temp4 = B[var2];
            C[i] = temp4;
        }
    }

The main for loop is designed so that one and only one value is added to the result matrix each time through. Take a look at the comments I had for this section again (there are 2 line comments, 1 line of code/comment, no other control structures needed).

Lastly, it's not necessary to create a temporary variable before setting it to another array (though technically there's nothing wrong with it) You can simply perform the assignment into the result array:

// Version 1: old code
int temp3 = A[var];
C[i] = temp3;
// version 2: New hotness (bonus points if you can name the movie :D)
C[i] = A[var];