Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Ticket #572 (new enhancement)

Opened 12 years ago

Last modified 10 years ago

Tango lacks a stable sort

Reported by: Deewiant Assigned to: Deewiant
Priority: normal Milestone: 1.0
Component: Core Functionality Version: 0.99 RC3 Xammy
Keywords: triage Cc:

Description

The C++ STL provides stable_sort, a stable sort.

Tango doesn't, even though it's quite handy to have in some cases. I've written an okay-performing (although it allocates O(n) extra space) merge sort, which can be found in sort.d over at Ticket #571. It could be improved, but it's better than nothing. It needs a little work before it's "ready to go", though: it needs to be templated (currently it uses just an alias), and a boolean template parameter to choose whether to sort to ascending or descending order.

I'm not sure whether it should have the option to take a predicate: if the predicate returns false for equal items, the sort isn't stable. At the very least, this needs to be documented.

Change History

08/15/07 16:24:40 changed by sean

  • status changed from new to assigned.

Thanks. I'd planned on adding a stable sort routine but wasn't sure of the best algorithm to use so I put it off and forgot about it. Merge sort is a decent option, though, so perhaps I'll use that. It presents a good opportunity to offer merge sort anyway, which some people may want to use instead of the in-place sort routine in some instances. I'll admit that was one reason I offered the heap routines as well--they provide heap sort "for free."

08/15/07 16:52:33 changed by Deewiant

Merge sort is generally considered the fastest stable sort there is. (Or at least, I haven't come across anything which even claims to be faster whilst preserving stability.)

The problem with it is that it uses O(n) storage, because it needs to merge the data into a temporary array. There are in-place merge sorts, but they're noticeably slower than the ones which use the storage, and notoriously harder to code.

It's up to you: as usual, I prefer the most general approach, which is to provide both in-place merge sort (the default stable sort) and merge sort taking an additional buffer argument. If the buffer is too small, it is resized to the length of the array being sorted.

One implementation of in-place merge sort can be found here: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html

05/24/08 19:17:58 changed by larsivi

  • keywords set to triage.

11/19/08 12:28:21 changed by larsivi

  • type changed from defect to enhancement.
  • milestone changed from 1.0 to 0.99.8.

03/29/09 13:34:10 changed by larsivi

  • status changed from assigned to new.
  • owner changed from sean to fawzi.
  • milestone changed from 0.99.8 to 0.99.9.

11/29/09 12:29:59 changed by fawzi

  • owner changed from fawzi to kris.

01/12/10 04:18:03 changed by kris

  • owner changed from kris to Deewiant.
  • milestone changed from 0.99.9 to 1.0.

Wanna update your stable-sort and add it in the appropriate place, Deewiant?