Thank you, the changes seem to solve the issue. Any idea when
IMP 5 is going to be released so we can try it out?

I think the issue is that you and I have different meanings for 
"arrival" sort.  See Ticket #8936 for a full recap.

In short, IMP 4.x is behaving correctly.  But that behavior can be 
improved/tweaked - hence the new ticket.  However, these changes will 
take place solely in IMP 5.  Thus, this ticket will remain as 'Not a 
Bug'.

On Fri, Mar 19, 2010 at 12:46:25PM -0400, bugs@horde.org wrote:
We use cyrus here and it implements ARRIVAL SORT by comparing internal
dates from the mailbox index (no need to read header of every message).
It also implements a SEQUENCE SORT that uses just message numbers:

         switch (sortcrit[i].key) {
         case SORT_SEQUENCE:
             ret = numcmp(md1->msgno, md2->msgno);
             break;
         case SORT_ARRIVAL:
             ret = numcmp(INTERNALDATE(md1->msgno), INTERNALDATE(md2->msgno));
             break;

Ok, but for those of use using servers like cyrus, perhaps there could
at least be a configuration option to select between _arrival cache
and ARRIVAL SORT?

Because it is the fastest sort.  All IMAP servers necessarily need to 
track their message sequence numbers, so sorting by this value is 
"free" (as opposed to date sort - this requires each message's header 
to be parsed to get the date value).
Yes.  ARRIVAL SORT = message sequence number.  This statement is 
nothing more than providing a keyword to use for SORT to do the same 
thing as a regular arrival sort.
_arrival cache does not to "pretend to implement this IMAP search 
type".  The arrival cache implements a cache of the message sequence 
numbers.

Arrival sort is on by default because it is the *only* sort that can 
reasonably be used on large mailboxes on ALL IMAP servers.

Unfortunately, you are assuming a lot of things about IMAP servers.   
First, the SORT extension wasn't standardized until June *2008*.  So 
there can be no assumption that the IMAP server supports SORT (not to 
mention IMP 4 was first released 5-6 years ago, before SORT existed on 
most IMAP servers).

Second, many IMAP servers don't support SORT.  It's not required of an 
IMAP 4rev1 server.  Thus, to sort by anything other than internal 
arrival time requires the IMAP server to parse *EVERY* header of 
*EVERY* message in the mailbox (a MUA can use FETCH to only return the 
text of the desired header, but this still requires the IMAP server to 
internally parse every header to collate this information).

Third, even for IMAP servers that support SORT, there is no guarantee 
that SORT is inexpensive.  Many IMAP servers may not cache this 
information, so every SORT call to the server requires parsing of the 
entire mailbox.

The issue with sorting a mailbox, at least with the original IMAP 
4rev1 spec, is that IMAP was originally designed to act in a connected 
environment.  Meaning that you logged on once in the morning and your 
e-mail client handled issues like sorting ONCE (since further changes 
could be caught via untagged responses since the IMAP client was 
always connected to the IMAP server).  IMAP was NOT designed for 
disconnected clients, such as webmail, that were constantly 
connecting/disconnecting from the server.  Tools have slowly been 
developed to help this situation (imapproxy, RFC extensions, webmail 
server caching) but usage of these tools can not be guaranteed in any 
single installation.

Thus, the only reasonable default sort is ARRIVAL.

But why would users be interested in IMAP servers internal info like 
message sequence number/UID? Looking at the IMAP SORT RFC 
(http://www.faqs.org/rfcs/rfc5256.html) I found the ARRIVAL sort type:

       ARRIVAL
          Internal date and time of the message.  This differs from the
          ON criteria in SEARCH, which uses just the internal date.

And this is exactly what gets called if I disable the IMP _arrival 
cache. So _arrival cache pretends to implement this IMAP search type 
but does something different - sorts on UID instead of IMAP internal 
date. As a result our users see messages that are almost randomly 
sorted. The worst thing is that arrival sort type is the default.

You have an incorrect assumption as to how IMAP arrival times work.   
Arrival sort, otherwise known as the message sequence number, is the 
order in which messages are received in that mailbox.  If you copy an 
old message into a mailbox, that message "arrived" in that mailbox at 
the time you moved it, not the time the original message was sent.

It sounds like you want date sort, not arrival sort.

It seems that IMP assumes that sorting the messages by UID is the same 
as sorting them by arrival date. But this is not always the case. For 
example if I copy an old message to an IMAP folder it will get a new 
high UID but the arrival date stays in the past and should be sorted 
accordingly. Disabling the special handling of SORTARRIVAL 
($imap_cache->getMailboxArrival) in imp/lib/Mailbox.php seems to solve 
the issue. Now IMP issues "UID SORT (ARRIVAL)" or "UID SORT (REVERSE 
ARRIVAL)" and messages appear properly sorted. Or perhaps the messages 
should be sorted by arrival date before putting them into the _arrival 
cache? There relevant part of the code:

                 if (false && $sortpref['by'] == SORTARRIVAL) {
                     require_once IMP_BASE . '/lib/IMAP/Cache.php';
                     $imap_cache = &IMP_IMAP_Cache::singleton();
                     $this->_sorted = 
$imap_cache->getMailboxArrival($this->_mailbox);
                     if ($sortpref['dir']) {
                         $this->_sorted = array_reverse($this->_sorted);
                     }
                 } else {
                     $this->_sorted = 
$imap_search->searchSortMailbox($query, null, $this->_mailbox, 
$sortpref['by'], $sortpref['dir']);
                 }