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.