Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

What is wrong with my merge sort implementation ?

java mergesort algorithms

This topic has been archived. This means that you cannot reply to this topic.
1 reply to this topic

#1 Aemara

Aemara

    CC Lurker

  • New Member
  • Pip
  • 6 posts

Posted 05 December 2015 - 03:58 PM

What is wrong my merge sort implementation ? The output is wrong.

public static Integer[] mergeSort(Integer[] a)  throws NullPointerException {
    	if(a == null)
    		throw new NullPointerException();
        return(mergeSort(a, 0, a.length-1));
    }
    
    /* Sorts the input subarray of Integers a[p...q] using MergeSort and returns result.
     * Sorting is stable.
     */
    private static Integer[] mergeSort(Integer[] a, int p, int q) {
    	
    	    if ( p == q)
    	    	return a;
    	    
    	    	  // Get the index of the element which is in the middle
      	      int middle = (q + p) / 2;
      	      // Sort the left side of the array
      	      Integer[] s1 = mergeSort(a,p,middle);
      	      // Sort the right side of the array
      	      Integer[] s2 = mergeSort(a,middle + 1, q);
      	      // Combine them both
      	       a = merge(s1,s2);
      	    
    	  return a;
    }
    
    /* Merges two sorted arrays of Integers into a single sorted array.  Given two
     * equal elements, one in a and one in b, the element in a precedes the element in b.
     */
    public static Integer[] merge(Integer[] a, Integer[] b) {
    	Integer[] s = new Integer[a.length + b.length];
        int i = 0;
        int j = 0;
        int k = 0;
        while(i != a.length && j != b.length)
        {
        	if(a[i] <= b[j])
        	{
        		s[k] = a[i];
        		k++;
        		i++;
        		
        	}
        	else
        	{
        		s[k] = b[j];
        		k++;
        		j++;
        		
        	}
        }
        
        while(i != a.length) 
        {
        	s[k] = a[i];
        	k++;
        	i++;
        	
        }
        while(j != b.length)
        {
        	s[k] = b[j];
        	k++;
        	j++;
        	
        }
        
        return s;
    }


#2 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts

Posted 05 December 2015 - 05:11 PM

In general, 2 things are wrong.

if ( p == q)

What that if-statement should do is: Decide when you should no longer split the array in 2, to create s1 and s2.

The answer here is: when the array is either empty, or when the array has only 1 element in it.

 

 

The 2nd thing going wrong is:

Integer[] s1 = mergeSort(a,p,middle);
Integer[] s2 = mergeSort(a,middle + 1, q);

Here the problem is that you should send only half of the array to the next mergeSort.

In case of s1 you should send the half from index 0 to middle, in case of s2 you should send the other half: from middle to the end.

 

 

Realisticly you don't really need your p and q variables. I would strongly suggest first cleaning that up like this (Code below still needs cleaning up of "p" and "q"), remove your first method on top with the nullpointerexception:

    /* Sorts the input subarray of Integers a[p...q] using MergeSort and returns result.
     * Sorting is stable.
     */
public static Integer[] mergeSort(Integer[] a) {    	
    	    if ( p == q)
    	    	return a;
    	    
    	    	  // Get the index of the element which is in the middle
      	      int middle = (q + p) / 2;
      	      // Sort the left side of the array
      	      Integer[] s1 = mergeSort(a);
      	      // Sort the right side of the array
      	      Integer[] s2 = mergeSort(a);
      	      // Combine them both
      	       a = merge(s1,s2);
      	    
    	  return a;
    }

Edited by wim DC, 05 December 2015 - 05:19 PM.