Merge sort

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

Image source

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)/2
left = arr[0:mid]
right = arr[mid:]

Then all implementation takes 24 lines.

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 startand endindexes, then using temporary array to merge sorted subarrays, and then using System.arraycopyto replace unsorted part with sorted.

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