Merge Sort algorithm in Java

This is a very simple Java implementation of the popular merge sort algorithm.
I decided to put this here because I needed to refresh my knowledge of sorting algorithms, problem is I could not find an easy-to-understand implementation online, so I decided to implement my own version and share it in case someone is struggling on understanding how to implement this algorithm. I think this is the shortest implementation ever.

Introduction

Merge sort works by splitting the original array into halves several times until many subarrays of size 1 are obtained.
The algorithm then merges back every subarray in such a way that the result of merging two subarrays is a single, sorted array twice as big as the subarrays.
The process is repeated until an array of the same size of the input array is obtained.

Here is an example:

             
              [24, 3, 17, 109, 6, 72, 11, 0]                  Unsorted input

      [24, 3, 17, 109]              [6, 72, 11, 0]            Split #1

   [24, 3]       [17, 109]      [6, 72]        [11, 0]        Split #2

  [24]  [3]     [17]  [109]    [6]  [72]      [11]  [0]       Split #3

   [3, 24]       [17, 109]      [6, 72]        [0, 11]        Merge #2
   
       [3, 17, 24, 109]             [0, 6, 11, 72]            Merge #3
           
              [0, 3, 6, 11, 17, 24, 72, 109]                  Merge #4 : Sorted output

This is a very simple introduction to the algorithm, more details on Wikipedia.

Give me the code!

Here’s the code I wrote that implements this merge sort, it can be improved a lot especially on the space it requires to run, you’ll see that at every iteration two new subarrays are created, this is not optimal if we need to save memory.

    public int[] mergeSort(int[] array) {

        if (array.length == 1) return array;

        int start = 0;
        int end = array.length;
        int middle = (end-start)/2;

        int[] left = Arrays.copyOfRange(array, start, middle);
        int[] right = Arrays.copyOfRange(array, middle, end);

        int[] sortedLeft = mergeSort(left);
        int[] sortedRight = mergeSort(right);

        return merge(sortedLeft, sortedRight);

    }

    private int[] merge(int[] first, int[] second) {

        int[] result = new int[first.length + second.length];

        int posFirst = 0;
        int posSecond = 0;
        int posResult = 0;

        while (posResult < result.length) {

            if (posFirst == first.length) {
                result[posResult++] = second[posSecond++];
            }
            else if (posSecond == second.length) {
                result[posResult++] = first[posFirst++];
            }
            else if (first[posFirst] > second[posSecond]) {
                result[posResult++] = second[posSecond++];
            } else {
                result[posResult++] = first[posFirst++];
            }

        }

        return result;

    }
Advertisements

One thought on “Merge Sort algorithm in Java

Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: