implement natural merge sort to have O(n) for already sorted lists

[hkiel]

[OpenModelica-Hudson]

The test suite is unstable according to OpenModelica_TEST_PULL_REQUEST 2017-10-10_12-15-02.

[OpenModelica-Hudson]

The test suite is unstable according to OpenModelica_TEST_PULL_REQUEST 2017-10-10_16-14-06.

[OpenModelica-Hudson]

The test suite is unstable according to OpenModelica_TEST_PULL_REQUEST 2017-10-12_14-59-45.

[hkiel]

@sjoelund The current merge sort implementation in List.sort is not stable. In fact it reverts the order of equal elements.

My natural merge sort implementation should however be stable but leads to failures in the test suite. E.g. simulation/libraries/msl32/Modelica.Fluid.Examples.HeatingSystem.mos does not compile anymore. Do you have any hint why this can be?

[sjoelund]

HeatingSystem is very sensitive to the order of elements. It's just some heuristics that choose a different path as far as I know.

[hkiel]

I still think that we should use a stable sort algorithm.