# Merge sort (Java)

**Other implementations**: ACL2 | C | C++ | dc | Erlang | Haskell |**Java**| JavaScript | Lisp | Oz | Perl | Python | Scheme

Merge sort or mergesort is a simple but efficient sort algorithm that splits the list into two sublists, sorts each one, then combines them into a single sorted list. It has good worst-case performance and requires only sequential access, making it ideal for sequential data structures like linked lists. In this Java example we'll write a simple mergesort for arrays.

The Java standard class library provides Arrays.sort() and Collections.sort() methods for sorting arrays and lists, respectively. They are implemented using mergesort. In practice you should use one of these instead.

In these examples we will demonstrate the sort only for *int*s; in the future this may be generalised to arbitrary data.

To sort an array using mergesort, we split the array into two subarrays in an implicit way:

<<simple array mergesort>>=publicstaticvoidmergeSortArray(int[]a,intstart,intend){check termination condition middle = start +(end-start)/2; mergeSortArray(a, start, middle); mergeSortArray(a, middle, end); merge the two sorted sublists}

The tricky part is merging the two sorted subarrays. We have two ways to go about this:

- Create a separate buffer the same size as the list for constructing the result of the merge in.
- Attempt to rearrange elements as we go so that the portion of the merged list constructed so far does not overwrite sublist elements that are not yet merged.

The first option is simple but has a high memory overhead (linear auxilary memory) as well as a problem with frequent allocations. The second option is in-place and more efficient, but also more complicated. Here we stick to the simpler method:

<<array mergesort>>=publicstaticvoidmergeSortArray(int[]a,intstart,intend){mergesortArray variable declarations check termination condition middle = start +(end-start)/2; mergeSortArray(a, start, middle); mergeSortArray(a, middle, end); merge the two sorted sublists into temp System.arraycopy(temp, 0, a, start, end-start);}

The `System.arraycopy()`

at the end puts the final result back in *a*.

The merge operation itself is straightforward. We have two pointers starting at the beginning of each subarray, and we continually copy the smaller value into the result array and advance that value's pointer:

<<mergesortArray variable declarations>>=int[]temp =newint[end-start];inti1, i2, tempi, middle;<<merge the two sorted sublists into temp>>=i1 = start; i2 = middle; tempi = 0;while(i1 < middle && i2 < end)if(a[i1]<= a[i2])temp[tempi++]= a[i1++];elsetemp[tempi++]= a[i2++];

If either pointer hits the end of its subarray before the other, the remaining values are simply copied from the remaining subarray:

<<merge the two sorted sublists into temp>>=while(i1 < middle)temp[tempi++]= a[i1++];while(i2 < end)temp[tempi++]= a[i2++];

As with other divide-and-conquer sorts, the simplest termination condition is when the list becomes of size one or less:

<<simple check termination condition>>=if((start-end)<= 1)return;

But more efficient is to switch to insertion sort for small enough lists, like this code from Insertion sort (C, simple):

<<constants>>=privatestaticfinalintminMergeSortListSize = 60;<<check termination condition>>=if((end-start)< minMergeSortListSize){/* Use insertion sort for small datasets. */for(inti=start; i < end; i++){intj, v = a[i];for(j = i - 1; j >= start && a[j]> v; j--)a[j + 1]= a[j]; a[j + 1]= v;}return;}

This completes the sort. We can try it out with this sample code, which generates a random array of a size specified on the command line, sorts it, then verifies that it is in order:

<<MergeSortArray.java>>=classMergeSortArray{constants array mergesortpublicstaticvoidmain(String[]argv){intsize = Integer.parseInt(argv[0]);int[]a =newint[size]; java.util.Random rand =newjava.util.Random(System.currentTimeMillis());for(inti=0; i<size; i++){a[i]= rand.nextInt()% size;}mergeSortArray(a, 0, size);for(inti=1; i<size; i++){if(!(a[i-1]<= a[i])){System.out.println("ERROR"); System.exit(-1);}}System.out.println("SUCCESS"); System.exit(0);}}

Download code |