Can you help with sorting algorithm?

Question

go

I started reading the basics of Tim Roughgarden's algorithms here, and the merge sort algorithm is given in the introduction. I implemented it like this .

But I really don't like the condition block in merge. But without it, sorting does not work :,(

Please help with advice on how to merge correctly.

Answer 1

1. You are lucky that the length of the array is exactly 8, that is, a power of two. Your algorithm is in no way adapted to the fact that at the next step the length of the array will be odd.
2. I don't know how arrays are sliced ​​and parameters are passed in Go, but I need to check how much extra memory is being re-allocated.
3. Again lucky - the left and right halves are consumed very evenly: one on the left - one on the right. If we take a sorted array { 1, 2, 3, 4, 5, 6, 7, 8 }, when we first spend the left half, then the right one, it should fail. In fact, array merging contains even more conditions, and on each comparison we put into the resulting array not two elements from different arrays, but one - a smaller one. And accordingly we shift one of the caret indexes.