in reply to Re^2: move all 0s in an array to the beginning keeping other elements order same
in thread move all 0s in an array to the beginning keeping other elements order same

Hi ikegami,

can you please explain why using the use sort 'stable'; pragma would be important? Admittedly, the sorting block is peculiar and treats non 0 values as equal so that non 0 values may be reshuffled in the process (as would be the case using quick sort). However, since Perl 5.8, the default sorting algorithm (merge sort) is inherently stable, so I would expect the order of non 0 values to be preserved. Is there anything that I am missing?

  • Comment on Re^3: move all 0s in an array to the beginning keeping other elements order same
  • Download Code

Replies are listed 'Best First'.
Re^4: move all 0s in an array to the beginning keeping other elements order same
by davido (Cardinal) on May 05, 2014 at 04:36 UTC

    Possibly the fact that sort internally uses a stable merge sort is an implementation detail, not a semantic guarantee. Specifying stable explicitly means that if the luck of implementation changes the semantics will still remain in tact.


    Dave

[reply]
      Thank you, Dave, for your answer, but I think that the merge sort algorithm is inherently stable, independently of its specific implementations. But you are probably right that it is better not to take any cnance and make sure that stability is guaranteed.
[reply]

        What I didn't state clearly in my previous comment is this:

        In the old days, Perl's sort used a QuickSort algorithm, and it was swapped out, replaced by a Merge Sort starting (if my memory serves) with Perl 5.8. This swap in the implementation of Perl's "sort" was done primarily to avoid the potential for QuickSort to go quadratic on some inputs. A secondary effect was that it provided a stable sort.

        However unlikely it is that Perl would ever switch again, and this time to an unstable sort, the fact that modern Perls have a stable sort is still just an implementation detail. By specifying "use sort 'stable'", you are making a declaration of what semantics you require, leaving nothing to chance. Additionally, it signals to a future maintainer that this code would not fly if deprived of a stable sort.


        Dave

[reply]

        [ Sorry, missed your reply. ]

        but I think that the merge sort algorithm is inherently stable

        But sort doesn't necessarily use merge sort. While it's currently the default, it hasn't always been, and it might not always be.

[reply]
[d/l]

In Section Seekers of Perl Wisdom