Merge sort on an Integer class

Question

This is a specific case in merge sort. I'm trying to do a merge sort on an array that's created using the Java Integer class. My implementation is slow and therefore needs some modifications for better performance. I believe the process where I copy the original items to two new arrays over and over again is slowing it down.

How do I merge sort without copying? The sorting must be stable and both methods should return Integer[].

private static Integer[] mergeSort(Integer[] a, int p, int q) 
{
 if (a.length <= 1) return a;
 int mid = (int)Math.floor((q-p)/2);
 Integer[] left = new Integer[(mid - p) + 1];
 Integer[] right = new Integer[q - mid];
 int index = 0;
 for (int i = 0; i < left.length; i++)
 {
 left[i] = a[index++];
 }
 for (int i = 0; i < right.length; i++)
 {
 right[i] = a[index++];
 }
 left = mergeSort(left, 0, left.length-1);
 right = mergeSort(right, 0, right.length-1);
 return merge(left, right);
}
private static Integer[] merge(Integer[] a, Integer[] b) 
{
 int i = 0; int j = 0; int k = 0;
 Integer[] result = new Integer[a.length+b.length];
 while (i < a.length || j < b.length)
 {
 if (i != a.length && j != b.length)
 {
 if (a[i].compareTo(b[j]) <= 0)
 {
 result[k++] = a[i++];
 }
 else
 {
 result[k++] = b[j++];
 }
 }
 else if (i < a.length)
 {
 result[k++] = a[i++];
 }
 else if (j < b.length)
 {
 result[k++] = b[j++];
 }
 }
 return result;

• mattedgod: The algorithm looks correct to me. Merge sort requires you to split the array which doesn't really happen without copying to two new arrays at some point so I don't think that's your issue. You could try doing it with an int[] instead of an Integer[]. Java might like its primitive types better
• Jakub Zaverka: Given that this is not a homework, why don't you just use the Arrays.sort() stuff? That is a merge sort. (Provided you convert array of Integers to array of ints, but that's just O(n), less than O(nlogn) merge sort.)
• user1175946: I can actually write two void methods for sorting ints but this question requires me to return an array of type Integer[].
• user1175946: @Jakub Zaverka: Arrays.sort is using quick sort. I'm trying to compare it with my program.
• Jakub Zaverka: @user1175946 Oh, good one, I thought they are using mergesort. Anyway, if you use sort(T[] a, Comparator<? super T> c), then it is mergesort (just checked). You only need to provide an implementation of Comparable<Integer>, which should be trivial.

Answer 1

It was quite hard, but I figured it out. You can even pre-create the buffer with some value you know the mergesort will never exceed, and save some object creation overhead.

public class Mergesort
{
 public static void main(String[] args){
 int[] array = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
 array = mergeSort(array, 0, array.length-1);
 for(int i = 0; i < array.length; i++){
 System.out.print(array[i] + " ");
 }
 System.out.println();
 }
 private static int[] mergeSort(int[] a, int p, int q) 
 {
 if (q-p < 1) return a;
 int mid = (q+p)/2;
 mergeSort(a, p, mid);
 mergeSort(a, mid+1, q);
 return merge(a, p, q, mid);
 }
 private static int[] merge(int[] a, int left, int right, int mid) 
 {
 //buffer - in the worst case, we need to buffer the whole left partition
 int[] buffer = new int[a.length / 2 + 1];
 int bufferSize = 0;
 int bufferIndex = 0;
 int leftHead = left;
 int rightHead = mid+1;
 //we keep comparing unless we hit the boundary on either partition
 while(leftHead <= mid && rightHead <= right){
 //no data in the buffer - normal compare
 if((bufferSize - bufferIndex) == 0){
 //right is less than left - we overwrite left with right and store left in the buffer
 if(a[leftHead] > a[rightHead]){
 buffer[bufferSize] = a[leftHead];
 a[leftHead] = a[rightHead];
 bufferSize++;
 rightHead++;
 }
 }
 //some data in the buffer - we use buffer (instead of left) for comparison with right
 else{
 //right is less than buffer
 if(buffer[bufferIndex] > a[rightHead]){
 //we overwrite next left value, but must save it in the buffer first
 buffer[bufferSize] = a[leftHead];
 a[leftHead] = a[rightHead];
 rightHead++;
 bufferSize++;
 }
 //buffer is less than right = we use the buffer value (but save the overwriten value in the buffer)
 else{
 buffer[bufferSize] = a[leftHead];
 a[leftHead] = buffer[bufferIndex];
 bufferSize++;
 bufferIndex++;
 }
 } 
 leftHead++;
 }
 //now we hit the end of either partition - now we have only two of them (buffer and either left or right)
 //so we do traditional merge using these two
 while(leftHead <= right && (bufferSize - bufferIndex) > 0){
 if(rightHead <= right && a[rightHead] < buffer[bufferIndex]){
 a[leftHead] = a[rightHead];
 rightHead++;
 }
 else{
 if(leftHead <= mid){
 buffer[bufferSize] = a[leftHead];
 bufferSize++;
 }
 a[leftHead] = buffer[bufferIndex];
 bufferIndex++;
 }
 leftHead++;
 }
 return a;
 }
}

I did not extensively test it, nor did I measure it. You can try that and post the results.

Answer 2

If performance is the only criteria that you want, then you can use threads to paralyze the merging part of it. To copy an array there is a simple way to use Arrays.copyOf().

Here is the code that includes thread and the use of array as reference:

Integer[] array;
public MergeSort(Integer[] array) {
 this.array = array;
}
public void run() 
{
 if (this.array.length <= 1) return;
 int mid = (int)Math.ceil((this.array.length)/2.0);
 Integer[] left = new Integer[mid];
 Integer[] right = new Integer[this.array.length - mid];
 left = Arrays.copyOf(array, mid);
 right = Arrays.copyOfRange(array, mid, array.length);
 Thread t1 = new MergeSort(left);
 Thread t2 = new MergeSort(right);
 t1.run();
 t2.run();
 try {
 t1.join();
 t2.join();
 } catch (InterruptedException e) {
 }
 merge(left, right);
}
private void merge(Integer[] a, Integer[] b) 
{
 int i = 0; int j = 0; int k = 0;
 while (i < a.length || j < b.length)
 {
 if (i != a.length && j != b.length)
 {
 if (a[i].compareTo(b[j]) <= 0)
 {
 this.array[k++] = a[i++];
 }
 else
 {
 this.array[k++] = b[j++];
 }
 }
 else if (i < a.length)
 {
 this.array[k++] = a[i++];
 }
 else if (j < b.length)
 {
 this.array[k++] = b[j++];
 }
 }
}
public static void main(String[] args) throws InterruptedException {
 Integer[] unordered = new Integer[]{12,1,34,22,13,54,2,6,3};
 MergeSort merger = new MergeSort(unordered);
 merger.start();
 merger.join();
 System.out.println(Arrays.asList(merger.array));
}