FAQ
PTAL

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.

Search Discussions

  • Dr Volker Dobler at May 30, 2013 at 12:13 pm
    PTAL

    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.
  • Rsc at May 30, 2013 at 3:48 pm
    Thanks very much for working on this.

    Could you please put the notes from your last message in the code so
    that others who show up and think there should be a different algorithm
    can see why this decision was made/

    I assume the n**1.16 is purely empirical? Does the paper say anything
    about the expected number of swaps?

    Thanks again.
    Russ

    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.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedMay 30, '13 at 12:13p
activeMay 30, '13 at 3:48p
posts3
users2
websitegolang.org

2 users in discussion

Dr Volker Dobler: 2 posts Rsc: 1 post

People

Translate

site design / logo © 2022 Grokbase