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.

Unique opportunity! Help a fellow grow his blog!

Hi there! If you’ve read this far maybe you think this was useful, or fun, or I don’t know what but for some reason You Got Here! Great! Please consider sharing this post with your network, I am trying to get The Code Butchery to grow so I can provide more content like this, will you help me in my journey? Thank you!

Share this

Comments

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.