Closed Bug 57898 Opened 20 years ago Closed 4 years ago

Secondary/Multiple sort (stable sort)

Categories

(MailNews Core :: Backend, enhancement)

enhancement
Not set

Tracking

(Not tracked)

VERIFIED FIXED
Thunderbird 3

People

(Reporter: akkzilla, Unassigned)

References

(Blocks 3 open bugs)

Details

(Whiteboard: [parity-OE])

Attachments

(5 files)

Received from a user:
--
A request for a "nice to have" feature on Messenger mail - sort on more
than one field.  I'd love to be able to mark some items to get them to
sort to the top and have the rest sorted by date...
--

A lot of mail programs have a primary and secondary sort (e.g. sort by threads,
then secondarily by something else) and it would be a nice feature for our
mailer to have.
I think putterman has another bug on this already.
Assignee: mscott → putterman
This is the only bug I could find on Secondary Sort so I'll add my ideas for a 
UI implementation here. This idea assumes that the following is true as stated 
by Seth in bug# 30747 "...the goal is to make it so that only top level messages 
are sorted and that everything else is by order received.".

a. When selecting the Thread icon it could sort in a default order, what order 
I'm not sure.

b.For a secondary sort:

Thread pane:
To define a second criteria, such as date, you could place the cursor on the 
thread icon, right click and the context menu would show the secondary criteria 
(i.e. date, subject...). If "date" is selected then it would display the 
messages threaded according to date. If subject is selected then it would 
display the messages threaded according to subject.

Menu options:
User could select View|Sort by|Thread. Maybe this Thread menu item could have a 
submenu displaying the secondary criteria (i.e. date, subject...).


I'm usually a fan of direct manipulation, but I don't think it's going to work 
in this case. I think you'll need a Sort dialog, invoked from a `Sort ...' item 
in the `View' menu.
QA Contact: fenella → laurel
*** Bug 80934 has been marked as a duplicate of this bug. ***
We shouldn't restrict to 2 levels of sorting, but allow n levels.

UI:
 From bug 80934:
> As for the UI, I could click on the From (labeled "Sender", grumble) column
> header first, then shift-click subject, then shift-click date. Or
> s/shift/Accel/.

ALternatively, when the user chooses a new sort criteria, make the current one
secondary, the currently second one gets tertiary and so forth.
Summary: RFE: Secondary sort → RFE: Secondary/Multiple sort
I agree with Ben Bucksch.

This feature doesn't need UI.  If I normally sort by date but decide to sort my
bugmail by subject, I unconsciously expect messages with the same subject to be
sorted by date.  When Mozilla mixes messages with the same subject in a
seemingly random order, I'm surprised and confused.  I shouldn't need to ask
Mozilla to "sort by subject and use date when the subjects are the same"; it
should do that automatically.

The very small percent of users who consciously want to sort on multiple
criteria will have already noticed the "stable sort" feature and will know how
to use it.  

Implementation note: "stable sort" doesn't have to mean "Mergesort instead of
Quicksort".  Multiple sort has the same effect as stable sort long as at least
one sort criterion is different for each message.  As long as date is somewhere
in the list of sort criteria, multiple sort should be stable.

Stable sort is parity-OE, by the way.
Summary: RFE: Secondary/Multiple sort → RFE: Secondary/Multiple sort (stable sort)
Whiteboard: parity-OE
*** Bug 148461 has been marked as a duplicate of this bug. ***
comment #5 is exactly how Outlook does multiple sort, perfect.  Any ideas on
what kind of changes are necessary to implement this?  This bug hasn't really
seen any constructive activity and I'd be willing to work on.
This is a piece of the suggestion from bug 148461

"A suggestion for implementing the multiple category sort is to add an item to
the "View -> Sort By" menu called "Custom..." or "Multiple..." which opens a
dialog box like the dialog used to define mail filters rules  (seen in Tools ->
Message Filters-> (select filter name) Edit -> Filter Rules).  This item would
display checked if a custom category sort is current to that folder.  If a user
clicks on a category heading in the message view or selects a single category in
the existing "View -> Sort By" menu then that custom sort is unchecked."
reassigning to ssu.
Assignee: putterman → ssu
I'm all for the solution in comment 5, namely shift-click column header to
prepend (or append - I could live with that, too) that column to the sort
criteria list. This would be great. As for the UI, I propose a smaller arrow for
all the non-primary sorted columns; I don't think we need to distinguish which
is second, third etc.

Please also allow shift-click (or ctrl-click) on the primary sorted column to
un-sort that column; this way, the "no sort" (i.e. sort by order received) is
easily reachable without the menu, and thus bug 123786 is also solved.
How about a number next to the up or down arrow indicating it's sort order
rather than different sized arrows (no number if only one column if sorted by
one column)?

I think there should be a menu item in addition to shift-clicking.  Not having
one is like having a menu item with no keyboard shortcut...
Depends on: 178323
No longer depends on: 178323
*** Bug 178323 has been marked as a duplicate of this bug. ***
(Here are my comments from bug 178323 which I filed, and marked DUP of this)

With stable I mean that if I first click on Column "Date" followed by column
"Priority", I would expect a sort by Priority, then Date. And if I click Date,
Flagged, Priority and Unread I would expect a sort by Unread, then by Priority,
then by Flagged, and then by Date.

A typical implementation is to use a stack. When a given column is pressed, it's
first removed from the stack and then pushed on the top. The sorting order is
then top-to-bottom on the stack.

For extra credits, the actual "stack" used for the folder is remembered. And
threading should just be one of the sort keys (over subject?).
Responding to comment 11:

No keyboard modifier should be required to do a stable sort.  The default action
for clicking a column should be to make that column the primary sort criterion
while retaining the other sort criteria.
Responding to comment 15:

OK, that's fine with me, too. Just remember to make a way to un-sort a column
(ctrl+click or shift+click, and also a menu item).
-Begin Personal Opinion-

I think that this bug (and perhaps some others like it) really isn't receiving
the attention it deserves. I mean, yes, there are a ton of other 'real' bugs
that need to be fixed, and yes, I realize that saying "FIX IT QUICK!" isn't very
productive - if I had the skills I would give it a shot. Perhaps someone who has
some free time (and doesn't want to tackle a major issue) could take this up?
(Fingers crossed - this bug's been open for two-and-a-half years already,
without a fix.)

My point is simply that as small of an actual 'technical' problem that this is,
it IS one of the (few) fairly major usability shortcomings with Mozilla Mail.
Mozilla Mail, as good as it's gotten, just won't be able to compete (in the
general user population) with other clients (eg: Outlook / OE) without some of
the simple UI things (like this) being fixed. It's a basic feature of most mail
clients and is something that would help to make the very important leap between
a technically functional product and a usable product (doing what people expect
it to be able to do). Mozilla Mail is technically functional, and contains some
very excellent technical features (that work! :-D ). But it's not yet fully
usable to the general population because of (unimportant?) things like this.
Perhaps this bug deserves a higher priority than an P3 / Enhancement with no
Target Milestone, even if that means postponing a couple of other 'technical'
bug fixes that the general user base will rarely encounter?

-End Opinion-
I second travis' opinion on the previous comment. It seems time to fix this. 
Second second.
there should be a XUL tree-widget multiple sorting bug blocking this one
is there any UI standard for multiple sort for listbox?
Summary: RFE: Secondary/Multiple sort (stable sort) → Secondary/Multiple sort (stable sort)
Re: comment 18 and comment 19. So much for the new bug etiquette
*** Bug 200753 has been marked as a duplicate of this bug. ***
*** Bug 196696 has been marked as a duplicate of this bug. ***
*** Bug 166881 has been marked as a duplicate of this bug. ***
*** Bug 217040 has been marked as a duplicate of this bug. ***
One should also be able to set ascending/descending on each sort field, so it
could be ascending for one and descending on another.

This seems related to my newly submitted Bug #217034, in that if done right, the
fix should for both kinds of symptoms.
*** Bug 220293 has been marked as a duplicate of this bug. ***
*** Bug 189622 has been marked as a duplicate of this bug. ***
Blocks: 222728
No longer blocks: 222728
*** Bug 222728 has been marked as a duplicate of this bug. ***
*** Bug 238631 has been marked as a duplicate of this bug. ***
Blocks: 231945
*** Bug 241964 has been marked as a duplicate of this bug. ***
Product: MailNews → Core
*** Bug 279608 has been marked as a duplicate of this bug. ***
*Continuous* Secondary/Multiple Sort

This may be obvious to all, but I just want to make sure it’s noted that IMHO
the sort should remain continuously in effect (or at least give me a preference
somewhere that lets me turn this on).

e.g. 1:  If I sort by “Read” with new messages at the top (why, oh why, is this
backwards by default?!?!?), and then read the newest message, when I click off
that message it should move down below the rest of the unread messages.  

e.g. 2:  If I sort by flag and change the flag of the message I’m looking at,
when I click elsewhere / new message, it should automatically sort that message
to the correct location based on the fact that there’s no flag.

In either case, I don’t think I should have to re-issue a “sort” command – it
should just automagically always sort.

My personal ideal world is to sort by Priority/Flag, Read, then Date/Order
Received so that I can see the highest priority messages, then the unread ones,
then the rest sorted by date.  I want this always to be true – I don’t want to
have to re-click something to make it go back into sorted order.
 
My deepest thanks to all of the uber-cool people working on this!!!
*** Bug 302427 has been marked as a duplicate of this bug. ***
One thing I have noticed is that Tbird sorts the messages by time recieved in the inbox instead of the Date sent.  When transferring messages from one folder to another they are sorted by the order that the message was added to the folder and not by the date sent/recieved.  So the messages seem out of order.
(In reply to comment #35)
> One thing I have noticed is that Tbird sorts the messages by time recieved in
> the inbox instead of the Date sent.  When transferring messages from one folder
> to another they are sorted by the order that the message was added to the
> folder and not by the date sent/recieved.  So the messages seem out of order.

Ahem... what you're describing is not sorting at all - the messages are in the order that they were put in their respective folders, i.e., they are unsorted. I prefer Seamonkey to FF&TB so I don't know how exactly one selects the sorting order in TB, but I'm pretty sure that at least by clicking on the column header, you can sort the messages by that very column. There's also probably a menu option for that.
My workaround is to label the marked threads then sort by Label, Ascending, and Threaded.

This is a bit of a pain :)

I have had a lot of OE users asking for this as they transition. 
Assignee: ssu0262 → nobody
Priority: P3 → --
QA Contact: laurel → backend
The correct and easy way to implement this is to use a stable sorting algorithm (e.g. merge sort). See http://en.wikipedia.org/wiki/Sorting_algorithm. 

For example, suppose I sort by name:

Before:

Tom | Lunch
Dick | Dinner
Harry | Breakfast
Tom | Breakfast
Dick | Breakfast

After:

Dick | Dinner
Dick | Breakfast
Harry | Breakfast
Tom | Lunch
Tom | Breakfast

Now I sort by subject:

Dick | Breakfast
Harry | Breakfast
Tom | Breakfast
Dick | Dinner
Tom | Lunch

Note that the three names with subject "Breakfast" are still sorted. 

This is the technique that Outlook and every other program with sortable columns uses. Every other one except Thunderbird, which merrily scrambles everything but the currently sorted column.

No dialogs are required--just a change in the sorting algorithm. 


I believe this would be implemented in our current code by remembering the old sort and using either the old sort column as a tie-breaker, or the previous index of the cur msg, in our comparison algorithm.
Assignee: nobody → bienvenu
> or the previous index of the cur msg, in our comparison algorithm.

Unless you actually store this, the "stability" would end at a restart.
Actually, it wouldn't work when you change folders either.
It would really be useful if it was possible to have a two level sort. I.e. I want to be able to display my messages sorted first by sender and second by date. I currently have over a hundred senders each with 10-100 emails. Finding a specific one gets quite tough with the random order one get if one sorts by sender at present.
I do have code working that does a secondary sort. I'm trying to generalize it to do a real multi-level sort.
Would love to see a two level sort operational
This implements a second level stable sort by default - it might be interesting to try on the trunk. Most of the changes will be needed anyway to do a more general multi-column sort, and some of them will be useful for doing other interesting things in sorting.
Attachment #269096 - Flags: superreview?(mscott)
Attachment #269096 - Flags: superreview?(mscott) → superreview+
I checked this into the trunk. We're not persisting the secondary sort yet - I probably have to decide if I'm going to do the full-on multiple column sort first, since that'll affect how sorts are persisted.
This builds on the previous patch. Now multiple level sorts can be persisted and restored, custom columns can participate in secondary sort, and the sort order is part of the multi-level sort. So, for example, you can sort descending by date, then sort ascending by flagged, and flagged messages will be at the top of the thread pane, sorted with the newest messages towards the top. If you flag messages that you need to deal with right away, we will keep the flagged messages at the top, instead of having them scroll out of view as new messages arrive. 

I haven't fully implemented sorts of more than two columns, though I've made it fairly easy to extend the code to do that. The other open issue is that restoring a secondary sort on a custom column doesn't work because the custom column handlers are installed by extensions after the initial sort when you open a view. I'm not sure how I'm going to fix that.
Attachment #274503 - Flags: superreview?(mscott)
Comment on attachment 274503 [details] [diff] [review]
[checked in]improvements for secondary sort

should this be a PRBool?

+bool MsgViewSortColumnInfo::operator==
Attachment #274503 - Flags: superreview?(mscott) → superreview+
I'll double check the bool vs. PRBool (it would silence a compiler warning) but I thought I did it this way because nsTArray wanted it for its compare operator.
Comment on attachment 274503 [details] [diff] [review]
[checked in]improvements for secondary sort

yup, it should have been PRBool. Checked in as such.
Attachment #274503 - Attachment description: improvements for secondary sort → [checked in]improvements for secondary sort
fix crash when secondary sort comparison is required in the case of a uint32 sort criteria (I saw this when running with the Received date patch, when the received date field hadn't been filled in for a lot of the messages)
Attachment #275119 - Flags: superreview?(mscott)
Attachment #275119 - Flags: superreview?(mscott) → superreview+
Attachment #275119 - Attachment description: fix crash regression → [checked in ]fix crash regression
Duplicate of this bug: 254128
It looks like it has a strong relationship with bug 348350:

https://bugzilla.mozilla.org/show_bug.cgi?id=348350


Currently I'm using TB2.0.0.9 and still missing this feature. From the comments above I it's not really clear to me what the exact status is?

Once there is a (beta) version in which it can be tested, please post a comment and I'll try it out!
Blocks: 348350
Duplicate of this bug: 374171
Duplicate of this bug: 420929
Blocks: 423488
Duplicate of this bug: 430661
What's the status of this? How can I test the stuff that was checked in?
This is becoming a bigger issue than it originally was.  

The built-in secondary sort is "Order Received".  If one choses to sort ones email by "status" (let's say), the secondary sort will be by "order received".  However through time, people are moving emails around from computer to computer, folder to folder, which is making the "order received" less and less chronological.  

We must find a way to add a secondary (and beyond) sort feature, less we start becoming the reason why people move to a different client.
Magnus, you can test this on the trunk - the secondary sort is now the previous sort. So if you flat sort by date (no threading), then sort by sender, the ties in the sender sort will be broken by comparing the date values. If you sort by sender, then sort by subject, the ties in the subject sort will be broken by comparing the senders.
Sorry for this noob question, but does 'on the trunk' mean that it's in the nightly builds?
yes, nightly builds, as well as the 3.0 alpha builds.
Mmm, very fine comments about a single simple stable sort. This is a shame these 60 comments and 8 years for a such simple thing. I suggest to stop comments, to take lessons form MS and to implement...
For those who need definitions about stable sort, please see http://en.wikipedia.org/wiki/Stable_sort#Classification
uh, so a single simple stable sort is implemented...
I want:
a) untreaded
b) newest messages are on the top
c) newest unread messages are on the top

So, when I mark a message as read it appers first at the top of read messages. Before this chick-in last years all worked fine when I sorted by "unread messages at the top". After this check-in it was broken.


How do I try to sort now:

a) press twice on the Data column, so newest dates are on top.
b) press Unread column twice, so on top are the newest unread messages and then after the unread one's the newest read messages.

It works fine. But till changing/reloading the folder. After reloading folder  unread stays on top, but descending, so newst read messages are at the bottom.

Look at the screenshot.

Should I fill a new bug?

BTW When setting unread and newest date at the bottom all works fine. The problem is only setting on the top.
Attached image The sorting problem
Eugene, that's a problem in the persistence of the sort order. I'll look into that...
when opening a folder again, sort_type and m_sortType won't have changed, but we still need to set m_secondarySort*.
Attachment #329928 - Flags: superreview?(neil)
Attachment #329928 - Flags: review?(neil)
(In reply to comment #63)
> uh, so a single simple stable sort is implemented...
> 
I am sorry, David, but no....
Steps to repeat:
1- select incoming folder
2- sort by sender
3- sort by "receiver" (I do not know the english word)
You note that the sender column is no more sorted (for the same receiver). It should be in "stable" sort.... (I use Thunderbird 2.0.0.14 on last Ubuntu). If I am not clear, please ask, I am ready to spend hours to well explain.
Pierre: the fix is trunk only (not 2.0.0.x).
ftp://ftp.mozilla.org/pub/thunderbird/nightly/latest-trunk/
(In reply to comment #64)

> b) press Unread column twice, so on top are the newest unread messages and 

The fact that when you have pressed the 'data' column twice to get sort 'top down' and after that also have to press the 'unread' column twice to get that to sort 'top down' too imo. already shows that it's not implemented right. It should (on first press) use the sort direction of the previous pressed sort column.
Trying this for the 'flagged' column however, showed that that does get the flagged messages at the top on one click... But changing folders still messes things up.

Fyi. Also fiddled around with the 'flag' and 'unread' and from that it becomes clear that the secondary sort is completely lost after a folder switch. Imo. the 'data' column changing directions is a coincidence caused by some other variable. 
Attachment #329928 - Flags: superreview?(neil)
Attachment #329928 - Flags: superreview+
Attachment #329928 - Flags: review?(neil)
Attachment #329928 - Flags: review+
Comment on attachment 329928 [details] [diff] [review]
[checked in]fix restoring secondary sort

again, this is all trunk only, not 2.0x.
Attachment #329928 - Attachment description: fix restoring secondary sort → [checked in]fix restoring secondary sort
Yes David, I did this with the latest TB3 'Shredder'.
Sorry, that was in response to Pierre's comment. To Mark, tomorrow's nightly build should have the secondary sort restored after a folder switch. Re the sort column direction, having the second click always follow the direction of the current sort may not be what users want, since it depends on the columns involved. E.g., if you want to sort by unread, with unread at top, i.e., reverse, and then sort by subject, I don't think you want subject to be reverse sorted by default.
I don't agree David. If the normal/forward sort on subject is bottom up, A > Z, then yes, I would like to have the subject reverse sorted when sorting other columns also top down/reverse.
Product: Core → MailNews Core
In the config editor I see an entry for "mailnews.default_sort_order" which is set to 1. Is there an alternate number that would make the default sort order for new folders "Order received + Descending"?
Jon Roland, Bugzilla is not a support forum. Please ask on mozilla.support.thunderbird.
Okay. Where is mozilla.support.thunderbird?

Consider the comment a request to make it an option to set "mailnews.default_sort_order" to a number which would make the default sort order
for new folders "Order received + Descending"
(In reply to comment #77)
> Okay. Where is mozilla.support.thunderbird?

see http://support.mozillamessaging.com/en-US/kb/
Sorting by multiple columns (in my case "order received" and "tag") used to work fine in TB 2.0.0.23/24 but it is broken for TB 3.* (up to 3.0.4 on Windows and Linux). Now the initial sorting in one folder does not even produce the correct result when selecting the second column to sort. When changing to another folder and coming back, then the first column ordering is lost completely. The issue becomes more critical with the new Linux distributions (e.g. Ubuntu 10.04 LTS) where TB 2 does not work anymore due to changes in core Linux libraries.
Same here, multiple sorting criteria has always been a need for me. With TB 2.x you could at least workaround this missing feature, now it becomes important to get it working.
Mmm, the bug seems to me solved in my 3.1.4 release
I tried out the Linux tar ball version of 3.1.4 today, but its multiple sort behavior when using columns "order received" and "tag" is still wrong in the way I described earlier (2010-05-26).
Duplicate of this bug: 639606
Duplicate of this bug: 631555
Duplicate of this bug: 695265
Duplicate of this bug: 582875
Hello!
what about fixing of this bug?
(In reply to Mikhail from comment #87)
> Hello!
what about fixing of this bug?

Are you volunteering?
No))) I am submitter of bug (dublicated of this - 582875) and wait if somebody fix it =)
Assignee: dbienvenu → nobody
mmm, At my knowledge, this bug is fixed
It doesn't. I use 13.0.1
Just tried 13.0.1 under Windows 7 64 Bit Home Premium and got the same buggy behavior as described in a previous report above.
Sorry, I have done your test on my french version and I have the same problem...
Mmm, I have refrained until now, but, seeing the answer of Gart to Mikhail, I  wonder if simple mortel people like Mikhail or me, neither programmer or geek, are allowed to use thunderbird and to express their needs, and their frustration to see so basic bug not taken in account since years...
Hello! 

any news about this issue?
Whiteboard: parity-OE → [patchlove][parity-OE]
I can confirm this behavior in latest 17.0.5 and 21b1 releases.
I'm trying to have the following sorting: "Starred (first) - Unread (second) - Date (third)": only the first two sorting are kept, not the third.

As far as I can remember, the old TB 15 this triple-sorting feature was working as expected!
"simply use stable_sort(), instead of NS_QuickSort()/morkQuickSort() which is non-stable sort" is normal and simplest first step of solution, isn't it?

QuickSort use in comm-central
> http://mxr.mozilla.org/comm-central/search?string=QuickSort&case=on
C++ std:sort() and std:stable_sort()
> http://www.cplusplus.com/reference/algorithm/sort/
> http://www.cplusplus.com/reference/algorithm/stable_sort/

If you worry about "performance impact by stable_sort in ordinal sort", I believe "parameter for std::stable_sort() or std::sort()/qsort()/NS_QuickSort()/morkQuickSort choice" is sufficient.
See bug 870556 comment #8 for quick measurement of sort routine call.
See Also: → 316301
It seems to me that the problem has been corrected in 24.0.1 release...
Just tried 24.0.1 under Windows 7 and it still does not work for me :-(
Same thing here, it still doesn't work :(
howdy y'all,

os = win7x32, sp1
tb = 24.0.1

perhaps i am not understanding this. it certainly seems to be working for me.

STR [Steps To Reproduce] 
- click twice on date column to sort newest on top
- click on from column to sort a to z

at this point things are sorted 1st by alfa [a->z] order and then by date [new->old] order.

is this not what this bug is about?

take care,
lee
It looks indeed like "date"/"from" does work. I was trying "order received"/"tag". That does not work here.
Thank you Lee__Daily, it works for me now with your STR, with "date" / "read/unread".
howdy Dirk Muders,

it looks like the "order rcvd" column is the problem. i can use any other two columns and the 2ndary sort works. if i try to use "order rcvd" as the 2ndary & any other column as the primary, it loses the "order rcvd" sort - there is no secondary sort.

take care,
lee

-ps
@ fourmi4x ... you are quite welcome! glad to help.
lee-
Duplicate of this bug: 580855
This bug can likely be closed, as it does implement stable and secondary sort.  However, the feature is undiscoverable, has no UI indicating the secondary sort or order, and needs lots and lots of clicks to get to the desired state.

A UI has been implemented in TotalMessage for anyone interested.  There are some backend quirks that are made more visible, such as unclear meaning of Ascending/Descending for the false/true or has none/has some sorts, and lack of secondary sort by custom column, but on the whole this patch works reasonably well.  The biggest problem is that certain sorts are deathly slow on very large lists and it's all main thread unfortunately.

http://totalmessage.mozdev.org/
std::stable_sort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=std%3A%3Astable_sort%28&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
std:sort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=std%3A%3Asort%28&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
stable_sort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=stable_sort%28&case=1&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
NS_Quicksort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=NS_Quicksort%28&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
morkQuickSort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=morkQuickSort%28&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
quicksort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=quicksort%28&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central
sort( in comm-central
 http://mxr.mozilla.org/comm-central/search?string=sort%28&case=1&find=&findi=&filter=^[^\0]*%24&hitlimit=&tree=comm-central

Reference : NS_Quicksort( in mozilla-central
 http://mxr.mozilla.org/mozilla-central/search?string=NS_Quicksort%28

If std::stable_sort is used for sorting, and if messages is sorted by messageKey, and if sort(stable sort) is executed on another thread column value on "msgHdrDB array sorted by messageKey)", it's sorted by another thread column value and duplictes are sorted in messageKey value. i,e. Secondaary sort is achieved, although user can't fully control it.
Why "simply use std::stable_sort()" is not done yet?
Too hard to use std::stable_sort()? Performance of std::stable_sort() is very bad?
Or std::stable_sort() is not usable for sorting of msgDBHdr array?
Even if std::stable_sort is not usable for sort of object, if messageKey->msgDBHdr table is held, sort messageKey array by messageKey, sort "subject string + messgeKey value", then get msgDBHdr from messageKey value in sorted order by "subject string + messgeKey value", is always possible and simple job, athough I think any object can be sorted as far as Compare function supports the object.

(In reply to alta88 from comment #106)
> This bug can likely be closed, as it does implement stable and secondary sort.
>  However, the feature is undiscoverable, has no UI indicating the secondary sort or order, 
> and needs lots and lots of clicks to get to the desired state.

Why following is not aacceptable?
   "sort at a column" is sort of 'items currently shown in a specific order'" by the clicked column value. 

Following is obtained by simply utilzing stable sort.
  - Sort by Subject, sort by Starred, sort by Date, sort by Subject => Sorted by Subject, Date, Starred
  - Because "Order Received" == messgeKey which is absolutely unique if non-search folder(non virtul folder),
    when sorted by "Order Received", state of "no secondary sort is applied" is obtained always.

> A UI has been implemented in TotalMessage for anyone interested. 
> There are some backend quirks that are made more visible,
> such as unclear meaning of  Ascending/Descending for the false/true or has none/has some sorts,
> and lack of secondary sort by custom column, but on the whole this patch works reasonably well. 

Are you talking about issue of "Sort of multiple Threads" vs. "Sort in a Thread"?
If so, it's indenpendent problem from stable/secondary sort, although "Sort of Threads/Sort in Thread" should be fully cared always.

> The biggest problem is that certain sorts are deathly slow on very large lists and it's all main thread unfortunately.

Is it actually due to slownes in "sort()", "std::sort()", "stable_sort()", "std::stable_sort()"?
If it's related to "sort() module", it's due to following, isn't it?
- NS_QuickSort : (a) Best case = O(N) , when already sorted in ascendng order.
                                  if already sorted in ascending order,  it's almost same as "Copy".
                            (b) Average case = O( N * logN )
                            (c) Worst case = O( N^2 )
- NS_QuickSort after fix of problem of (c) : (d) Always O ( N * logN )
Because (a) is changed to (d), someone says "Slow".

If so, why NS_QuickSort is still used?
Because of (a), even if NS_QuickSort() is blindly used, it's fast, so,  because many array is already sorted in ascending order in many cases, someone says NS_QuickSort() is pretty quick?
However, msgDBHdr in gDBView is sorted as shown in Thread Pane. So, sort by a colimn is O( N logN ) in average in any sort module. Added cost by "stable sort" is "cost by stable" only.

Please don't confuse (i) "performance of sort()" with (ii) "performance issue in Tb's logic used in sorting elements is specific order".
Above (c) is problem in previous version of NS_QuickSort, but many performance issue is caused by (ii) instead of (i).
Needless to say, "Sort is expensive job" should be always counted.
(In reply to Lee_Dailey from comment #101)
> is this not what this bug is about?

As known by comment #45, comment #46, comment #47, "secondary sort" is already implemented and available.
Outstanding issue is "stable sort" part of "secondary and stable sort".
"Stable sort" is needed when duplicates exist.
 non-stable :  (1) Sort by Date  -> (2) Sort by Starred =>  "Order of Starred mails of same Date header at (1)" is changed by (2).
 stable :         (1) Sort by Date  -> (2) Sort by Starred =>  "Order of Starred mails of same Date header at (1)" is kept by (2).

Because "Order Received"=messageKey which is absolutely unique in a message folder, if "Order Received" is always counted by Compare function if duplicates, stable_sort() is not needed.
However, if Search Folder(Virtual Folder), "duplicate messaageKey" can happen. So, stable_sort() is still needed.
If "duplicate in multiple column sort" && "duplicate messageKey", if FolderName and AccountID is counted additionally, stable_sort may not be needed, because "accountID + MboxName + messageKey" is absolutely unique in Thunderbird.

(In reply to Dirk Muders from comment #102)
> It looks indeed like "date"/"from" does work. I was trying "order received"/"tag". That does not work here.

As I wrote, "Order Received" column value = messageKey which is absolutely-unique primary key in a message folder.
So, Order Received(messageKey) can't be a secondary sort column.

"Sort order by tag" is not "alphabetic order of string of tag which is shown at left most position in Tag column".
See bug 522212, bug 528034.
Default of sort order is alphabetic order of tagname which is ???? part of tag definition of mailnews.tags.????.tag = Important.
And there is no UI to change "sort order of tag" in Tb.
Tag of Important, Later etc. is defined as mailnews.tags.$laabelN.tag, so sorted by order like Important, Work, To Do, ....
I don't know about "order of tags in tag column of a mail".  It may be shown in "order of tag held in X-Mozilla-Keys:" or "order of imap flags returned from server", but it may be sorted by "tagname" at Thread pane.

For display in Threaded mode.
-  Order of mails in a Thread shouldn't be affected by sort column choice.
        Order of mails in a thread should be always determined by References  header.
        If no  References/Reply-To header, and if "mail of same subject after removing Re:" is merged into a thread,
        order should be determined by Date: header.
        Because "a thread" is flow of mail, flow of send -> reply -> reply ...,  no aascending/descending in "order in a thread".
- "Sort by column value" should be applied to "root mail of thread" only if Threaded mode.
Correction. "secondary sort" was finally provided by comment #71.

Currently, two column is used, previously selected one, and currently clicked one, and sort edby them.
Following is not possible?
1. use std::sort() for sort.
    stable sort is similar to :  if a==b, Compare function returns 
               "a<b" when "initial row number of a" < "initial row number of b",
               "a>b" when "initial row number of a" > "initial row number of b".
2. Because msgDBHdrs held in gDBView is already sorted in "currently displayed order at Thread Pane",
    simply sort "msgDBHdrs held in gDBView" by newly clicked column using stable sort,
    and replace gdbView.MessageHeaderArrayAtThreadPane by sortted one.
    Previous version of "msgDBHdr list" is freed by garbage collector sooner or later.
    "msgDBHdrs held in gDBView" is pointer array(array of reference), so memory consumption is not so large.
3. Because "accountID + MboxName + messageKey" is always absolutely unique in Thunderbird,
    following by Compare function may be used as alternative of stable sort in sort of msgDBHdr table.
      if a==b, Compre function  returns 
        "a<b"  when "accountID_a + MboxName_a + messageKey_a" < "accountID_b + MboxName_b + messageKey_b",
        "a>b"  when "accountID_a + MboxName_a + messageKey_a" > "accountID_b + MboxName_b + messageKey_b".


This kind of internaal soting may be a solution of "incorrect/unexpected threading when Search Folder with multiple search target folders".
So what is the conclusion here? Is sorting by 2 columns (secondary sort) implemented in this bug?
Is stable sort implemented? Even though I do not think stable sort is needed if secondary sort is implemented. Stable sort by itself does not fix this bug, because it is only a temporary solution. It breaks when switching folders or when new message come in.
So it seems to me this bug implemented secondary sort to overcome these problems. Just that it works silently without any UI. Is this enough to close this bug?
Do we open a new one (or use 1037857 or similar) to request more than 2 levels of sorting?
Comment on attachment 269096 [details] [diff] [review]
[checked in]implement 2nd level sort

Seems checked in in comment 46.
Attachment #269096 - Attachment description: implement 2nd level sort → [checked in]implement 2nd level sort
There seem to be no more incomplete patches needing love.
Whiteboard: [patchlove][parity-OE] → [parity-OE]
Duplicate of this bug: 346643
Removing myslef on all the bugs I'm cced on. Please NI me if you need something on MailNews Core bugs from me.
This bug is complete regarding secondary sort.  Any discussion of sort algorithm, or multiple sorts, or any followup should be moved to existing or new bugs.
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
An issue with a long history...

I'm having a hard time understanding what is supposed to be fixed or not. For my current version of thunderbird (38.6.0) secondary sort (star then date) works fine in non-threaded mode (although as you mentionned there is no user feedback about what the current secondary sort criteria is) however it is not the case in threaded view. Switching folders seems to completely mess up the secondary sort. Cf http://superuser.com/q/1042173/328283 for a description

Is this a different issue or still the same ?
In 38.5.1 on Ubuntu 12.04 LTS the secondary sort of the "Order received" and "Tag" columns still does not work. The second sort destroys the order of the first one. "Date" and "Star" do work, as you said.
(In reply to Dirk Muders from comment #117)
> In 38.5.1 on Ubuntu 12.04 LTS the secondary sort of the "Order received" and
> "Tag" columns still does not work. The second sort destroys the order of the
> first one. "Date" and "Star" do work, as you said.

This bug is *done* - no further action will occur here. Please file a new bug report ;)


(In reply to Cyril DD from comment #116)
> An issue with a long history...
> 
> I'm having a hard time understanding what is supposed to be fixed or not.

comment 59 is the behavior that is implimented. 

> For my current version of thunderbird (38.6.0) secondary sort (star then
> date) works fine in non-threaded mode (although as you mentionned there is
> no user feedback about what the current secondary sort criteria is) however
> it is not the case in threaded view. Switching folders seems to completely
> mess up the secondary sort. Cf http://superuser.com/q/1042173/328283 for a
> description
> 
> Is this a different issue or still the same ?

Whatever your issue may be, it needs a new bug report. But first I suggest you search this bug report for some key words, like "threaded" and "star", to get a sense of what has already been stated.
Status: RESOLVED → VERIFIED
Target Milestone: --- → Thunderbird 3
You need to log in before you can comment on or make changes to this bug.