Merge sort failure

[Rahul Sudip Bose]

I am trying to develop a merge sort program on my own. I need it for another program. Everything works well, except last step. Please help me to solve this issue.
If the implementation of the idea is faulty, please let me know.

Basic overview of my code :

Note that duplicate data in the array is allowed.

CLASSES :

1. MergeSort -
It will take a float array, make a copy of that array and then perform merge sort on it using an inner class called "Bin". This class has main method.

2. Bin -
It has a float[] data, 3 references of type Bin. 1st ref is lhs , ie the left half of float[] data. 2nd is rhs. 3rd is parent which refers to the object of which it is a fragment.
It has a method split, which splits the given array into half. This method also makes a call to ITS merge method to do the merging.
Show method is to see the contents of float[] data of a Bin.

The code :

public class MergeSort
{
	Bin toSort;
	
	public MergeSort(float[]take)
	{
		//preparing to sort the given array.
		int size = take.length;
		float[]copy = new float[size];
		for(int i = 0; i<size ; i++){copy[i]=take[i];}
		toSort = new Bin(copy);
		toSort.parent = toSort; // it is its own parent.
		
		//the merge-sort process begins.
		toSort.split();
		System.out.println("NOW THE SORTED ONE IS !\n");
		toSort.show();
		
	}//constructor
	

	public static void main(String[]args)
	{
		System.out.println("\nRunning main...\n");
		float[]test = {5.5f , 2.2f , 6.6f , 3.3f , 4.4f , 1.1f};
		MergeSort start = new MergeSort(test);
		System.out.println("\nMain ends.");
		
	}//main


	class Bin   // inner class of MergeSort.
	{
		Bin parent;
		float[]data;
		Bin lhs, rhs;
	
		Bin(float[]take)
		{
			data = take;
		}
	
	
		public void split()
		{
		
			int size = data.length;
			if(size>1)
			{
		
				int left = (size+1)/2; // to ensure lhs size >= rhs size.
				int right = size-left;
			
				float[]L = new float[left];
				for(int k = 0 ; k < left;k++){L[k] = data[k];}
					
			
				float[]R = new float[right];
				for(int k = 0; k < right ; k++){R[k] = data[left+k];}
					
		
				lhs = new Bin(L);
				lhs.parent = this;
			
			
				rhs = new Bin(R);
				rhs.parent = this;
			
			
				lhs.split();
				rhs.split();
		
				rhs.merge(rhs);

			}//if
		
		}//split 
	
	
	
	public void merge(Bin right) 
	{
	
		float[]above = right.parent.data;
		int t = 0;
		
		float[]RHS = right.data;
		int r = 0;
		
		float[]LHS = right.parent.lhs.data;
		int l = 0;
		
		
			//while both arrays have elements to consider.
			while(r < RHS.length && l < LHS.length)
			{
				if(RHS[r] != LHS[r])
				{
					if(RHS[r]<LHS[r])
					{
						above[t] = RHS[r];
						t++;
						r++;
					}else
					{
						above[t] = LHS[l];
						t++;
						l++;
					}
				
				}else //when both elements are equal.
				{
					above[t] = RHS[r];
					t++;
					above[t] = RHS[r];
					t++;
					r++;
					l++;
				}
			}//while
			
			// when no more elements to be considered in rhs.
			while(l < LHS.length)
			{
				above[t] = LHS[l];
				t++;
				l++;
			}
			
			// when no more elements to be considered in lhs.
			while(r < RHS.length)
			{
				above[t] = RHS[r];
				t++;
				r++;
			}	

// this is test code, only to see how code works !			
System.out.println("\t\t\tMERGER !!!\n\nTo merge :");			
right.show();
System.out.print(" , ");
right.parent.lhs.show();
System.out.println("\n\nPARENT : ");
right.parent.show();
System.out.println("\n");
		
	}//merge method.

	public void show()
		{
			for(int i = 0; i<data.length ; i++)
			{
				System.out.print(data[i]+ "  ");
			}//for
		
		}//show()
	
	
	}//class-Bin

}//class-MergeSort

[Rahul Sudip Bose]

The output of this code :

The last line is wrong. Everything before that looks ok.

Running main...

                        MERGER !!!

To merge :
2.2   , 5.5

PARENT :
2.2  5.5

                        MERGER !!!

To merge :
6.6   , 2.2  5.5

PARENT :
2.2  5.5  6.6

                        MERGER !!!

To merge :
4.4   , 3.3

PARENT :
3.3  4.4

                        MERGER !!!

To merge :
1.1   , 3.3  4.4

PARENT :
1.1  3.3  4.4

                        MERGER !!!

To merge :
1.1  3.3  4.4   , 2.2  5.5  6.6

PARENT :
1.1  3.3  4.4  2.2  5.5  6.6

NOW THE SORTED ONE IS !

1.1  3.3  4.4  2.2  5.5  6.6 // ARRRRR !!! THIS IS NOT CORRECT !!! WHY ??? :(
Main ends.

[Paul Clapham]

You have output which looks like this:

Candidates :  
6.6   , 2.2  5.5

Here I see two groups of numbers separated by a comma. In all instances except the last, there is no overlap between the two groups of numbers. To put it another way, every number in one group is larger than every number in the other group.

So my question is, is "every number in one group is larger than every number in the other group" supposed to be a result of your algorithm at every step? It appears that you are making that assumption when you combine the two groups. If that's the case, then there is something wrong with the part of the algorithm which produces the groups in the first place, and looking at the very end is the wrong approach. It's just that the problem doesn't show up until then.

However if that isn't an assumption you are making, then your method of combining the groups should merge them properly instead of simply assuming they can be concatenated.

[Rahul Sudip Bose]

I wonder why it works well till the last step. Any place that gives clear code with detailed explanations ??? (Giving up because my approaches are producing junk.)

PS :
I though that algorithms are supposed to be fun, but its depressing, especially due to esoteric books like cormen.

[Paul Clapham]

Rahul Sudip Bose wrote:I wonder why it works well till the last step.

Just luck. Try it with a larger and more unordered array as your input.

Any place that gives clear code with detailed explanations ??? (Giving up because my approaches are producing junk.)

I'm sure that a Google search would lead to all kinds of pages about sorting.

I though that algorithms are supposed to be fun, but its depressing, especially due to esoteric books like cormen.

Different people have different ideas about what is fun. I'm sure if you got up and went out into the street and asked the first 100 people you met whether designing a sorting algorithm would be fun, you would get at least 99 "No" answers.

(Which is also the reason I haven't spent any time looking at your code. I'm perfectly willing to help you out by asking questions to push you in the right direction, though.)

[Rahul Sudip Bose]

Back to the drawing board then.