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)/2
left = 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
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
end/2which led to endless loop when
start = 2and
end = 4, and one more at line 21 calculating
e1 + 1 (it should be just
e1, end index is exclusive — I pass array.length as initial end).