•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

• JackJames

hi i am jack i am seo expert jack james would love you to read new post

# 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 Aemara

Aemara

CC Lurker

• New Member
• 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
• 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.