Experimenting with several merging and rotation

algorithms convinced me that SymMerge with the simple

block swapping as rotation works very well:

- Stable sorting 10 million random integers is

only slower by a factor of ~5.5.

- The used algorithms are dead simple (at least if

compared to some fancy published stuff).

- Clean room implementations where trivial.

- The sorting is provable stable on _all_ input.

- Recursion depth (and thus required extra memory

for the stack) is limited by log(n).

- Calls to Less show O(n log n) behavior while

calls to Swap grow like O(n**1.16) which is worse

than the theoretical lower bound but not really

bad.

Better algorithms:

- Practical in-place mergesort

Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola

Nordic Journal of Computing 3,1 (1996), 27-40

The given algorithms are in-place, ops grow as

n log n

but _not_ stable.

- Fast Stable In-Plcae Sorting with O(n) Data Moves

J.I. Munro and V. Raman

Algorithmica (1996) 16, 115-160

Needs additional 2n bits but works only if there

are enough different elements available to encode

some permutations which have to be undone later.

All the optimal in-place sorting/merging algorithms

I found are either unstable or rely on enough different

elements in each step to encode the performed block

rearrangements. See also "In-Place Merging Algorithms",

Denham Coates-Evely, Department of Computer Science,

Kings College, January 2004 and the reverences in there.

https://codereview.appspot.com/9612044/

--

---

You received this message because you are subscribed to the Google Groups "golang-dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.