www.heteroclinic.net
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.
|
||
In Place Merge Sort 2 201702
When we have a proper way to do the merge, we can formalize the sort algorithm.
|
||
In Place Merge Sort 3 201702
The following code is the concrete implementation and test cases.
|
||
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.
|