Heteroclinic.net logo

www.heteroclinic.net

Algorithm Design Exercise
In Place Merge Sort 1

201702

In this exercise, we formalize the in place merge sort algorithm without recursion. It is also based on the in place array segments swap algorithm.

First, we give an algorithm about how to merge two sorted segments into one sorted segment. The segments may be discretely located.

Algorithm Design Exercise
In Place Merge Sort 2

201702

When we have a proper way to do the merge, we can formalize the sort algorithm.



Algorithm Design Exercise
In Place Merge Sort 3

201702

The following code is the concrete implementation and test cases.



Algorithm Design Exercise
In Place Merge Sort 4

201702

The time complexity is pending for discussion, it should be O(n log^2 n). The implementation is not very efficicient, it is far slower than the made libaray in Java, e.g. Arrays.sort(int []), which at the same time is a good caliber about the work we are doing about getting something 'made'. We need a good profiler and tester to improve the implementation. Previously, the solution of Magic Hexagon was boosted to 10s from five minutes by a seasoned profiler. We also know merge sort is best at utilizing parallelism.