# Merge sort

It’s a good exercise to implement basic algorithms such as binary search, heap, binary search tree, quick sort, merge sort…

Today I’ve decided to implement merge sort and since it’s an easy algorithm my estimation was to spend 20–25 minutes to do so (that includes whiteboard coding, quick manual test, coding mock implementation, coding test cases, failing tests, coding implementation, passing tests). However it took me 1 hour to get all tests green.

The problem was with Java’s array. Straightforward approach as you know is following:

• Split array in two parts
• mergeSort first part
• mergeSort second part
• create new array and fill it with sorted numbers from first sorted part and second sorted part

How to split array to two parts? This could be done easily in python:

`mid = len(arr)/2left = arr[0:mid]right = arr[mid:]`

It’s not that easy in java. Anything related to arrays in java is super inconvenient. So to avoid all this messiness I decided to try to do it in-place. And turns out that is not that easy.

Eventually I was able to avoid this ugly splitting by passing `start`and `end`indexes, then using temporary array to merge sorted subarrays, and then using `System.arraycopy`to replace unsorted part with sorted.

I did one silly mistake at line 19 calculating `e1`as `end/2`which led to endless loop when `start = 2`and `end = 4`, and one more at line 21 calculating `s2`as `e1 + 1` (it should be just `e1`, end index is exclusive — I pass array.length as initial end).