12

It is mentioned on Wikipedia that this method sorts an array in O(n log n) time, but it is also stable and in-place. That sounds like a very good sorting algorithm, since no other sorting algorithm does all of those at once (Insertion Sort isn't O(n log n), Heap Sort isn't stable, Quicksort (or Introsort) isn't either in place or stable, Mergesort is not in-place). However, on wikipedia only it's name is mentioned and nothing else. As a reference it goes to Franceschini, Gianni (1 June 2007). "Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves". Theory of Computing Systems 40 (4): 327–353. However, that doesn't really explain how it actually works, it shows more of why it exists.

My question is how does this method work (what steps does it actually do), and why are there so little resources related to it, considering there are no other known O(n log n) stable in place methods of sorting.

arin
  • 1,774
  • 22
  • 35
Costea Vlad Alexandru
  • 163
  • 1
  • 8
  • 1
    [Who says merge sort is not in-place?](http://stackoverflow.com/a/15657134/580412) – phs Mar 13 '14 at 21:12
  • 3
    in-place merge sort exists, however it is no longer O(n log n), it become O(n log^2 n) – Costea Vlad Alexandru Mar 13 '14 at 21:13
  • [Here's the paper.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.5336&rep=rep1&type=pdf) – phs Mar 13 '14 at 21:57
  • I hadn't heard of this one before. Interestingly, there doesn't appear to be any implementations around on the web. Perhaps there is something to that method, which makes it unappealing for real-life use. – 500 - Internal Server Error Mar 13 '14 at 22:30
  • 1
    @500-InternalServerError: Yes, that it's slow ;) Probably the constant factor is so large that even in-place merge sort is faster in practice – Niklas B. Mar 13 '14 at 23:33
  • O(n log(n)) in-place mergesort exists. I believe this was first discovered by Kronrod in 1969; there have been lots of developments since and most of them are linked by phs. – tmyklebu Mar 14 '14 at 00:40
  • @user2015213: Whoa, today I learned that log² *n* does not mean what I thought it did! – ruakh Mar 14 '14 at 01:14
  • @ruakh, yeah, *O(n log log n)* comparison sort is unfortunately not possible :( – Niklas B. Mar 14 '14 at 01:35
  • @NiklasB.: Yup -- that's what made me realize that user2015213's comment couldn't mean what it sounded like to me. (Well, that and the fact that O(*n* log log *n*) is already o(*n* log *n*) to begin with.) – ruakh Mar 14 '14 at 01:48
  • Does anybody know if there is any code that actually implements this FRANCESCHINI algorithm anywhere? Or is is just a theoretical algorithm that nobody even implements because its so complicated? – Brian Wiley Sep 15 '19 at 14:42

3 Answers3

3

considering there are no other known O(n log n) stable in-place methods of sorting.

It's sufficiently easy to implement merge sort in-place with O(log n) additional space, which I guess is close enough in practice.

In fact there is a merge sort variant which is stable and uses only O(1) additional memory: "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola. It has an optimal O(n log n) runtime, but it is not optimal because it uses Ω(n log n) element move operations, when it can be done with O(n) as demonstrated by the Franceschini paper.

It seems to run slower than a traditional merge sort, but not by a large margin. In contrast, the Franceschini version seems to be a lot more complicated and have a huge constant overhead.

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
1

Just a relevant note: it IS possible to turn any unstable sorting algorithm into a stable one, by simply holding the original array index alongside the key. When performing the comparison, if the keys are equal, the indices are compared instead.

Using such a technique would turn HeapSort, for example, into an in-place, worst-case O(n*logn), stable algorithm.

However, since we need to store O(1) of 'additional' data for every entry, we technically do need O(n) of extra space, so this isn't really in-place unless you consider the original index a part of the key. Franceschini's would not require to hold any additional data.

Gilthans
  • 1,656
  • 1
  • 18
  • 23
0

The paper can be found here: https://link.springer.com/article/10.1007/s00224-006-1311-1 . However it's rather complicated, splitting into cases as to whether the number of distinct elements is o(n / (log n)^3) or not. Probably the hidden constants make this an unattractive solution for sorting in practice, especially since sorting usually doesn't have to be stable unless secondary information is being stored in elements to be sorted which needs to be preserved in the original order.

Community
  • 1
  • 1
user2566092
  • 4,631
  • 15
  • 20