arsort() not stable

Question

Note! This question is outdated (thanks mickmackusa).

Edit: This question seems to be a duplicate of Preserve key order (stable sort) when sorting with PHP's uasort

Someone has been using arsort() to sort an array parsed from HTTP_ACCEPT_LANGUAGE under the assumption that it is a stable sort. But it's not: https://bugs.php.net/bug.php?id=53553. Now I have a bug and I am a bit at a loss how to fix the bug without resorting to hacks.

I have this header from a mobile client:

HTTP_ACCEPT_LANGUAGE: de-CH, en-US

and this gets parsed to:

Array (
    [de-CH] => 1
    [en-US] => 1
)

After parsing arsort($array, SORT_NUMERIC) is used to sort the languages corresponding to their q values. But because German and English has the same q value, arsort() swaps German and English. How can I sort the array so that the insertion order is preserved?

*"swaps German and English"* so `array('en-US' => 1, 'de-CH' => 1)`; I don't understand the difference? You want to keep the current order because both their values are equal? — Mike B, Aug 06 '12 at 20:23
It's showing the English version of the website to German users of the mobile phone. — nalply, Aug 06 '12 at 20:24
Use `usort()` then with a custom callback. And/Or use a workaround and assign slighly decreasing values (0.9999, 0.9998, 0.9997) as unspecified weights, instead of 1.0 — mario, Aug 06 '12 at 20:26
I still don't understand the use-case.. you can't 'parse' the HTTP_ACCEPT_LANGUAGE string with `arsort()`. Can you provide a simple array, expected and actual sorting results? You have pieces of each but not a complete, working example. — Mike B, Aug 06 '12 at 20:27
`usort()` is also not stable. PHP says: Note: If two members compare as equal, their relative order in the sorted array is undefined. — nalply, Aug 06 '12 at 20:28
Oh well, true. Seems you need a custom sorting function then: http://stackoverflow.com/questions/4353739/preserve-key-order-stable-sort-when-sorting-with-phps-uasort — mario, Aug 06 '12 at 20:35
@nalply: You can implement a stable sort if you want, but you're completely missing the point of q values in the spec. If a client sends equal q values for multiple languages, then _it does not prefer one over the other_. You're trying to fix a phantom problem. If a user is complaining, then that user needs to configure his/her browser such that the primary language is German, instead of German/English so that it sends the proper header values. — FtDRbwLXw6, Aug 06 '12 at 20:43
No, it is not a phantom problem. I and a friend reproduced it. When we configure the mobile phones as German, we are redirected to the English version of the website. Perhaps Samsung has a bug here but we cannot change Android here, can we? — nalply, Aug 06 '12 at 20:45
@nalply: If you're receiving an `Accept-Language` header with the value `de-CH, en-US`, then you did not "configure the mobile phones as German." You configured them as German/English. Whether or not the browser itself tacked on the English language, or whether you didn't specify priority when configuring, I couldn't say, but the problem is **client-side** not server-side. — FtDRbwLXw6, Aug 06 '12 at 20:49
@nalply: The order of languages in the `Accept-Language` header is not guaranteed to be sorted (hence the q values; if it were sorted by priority, q values wouldn't be necessary). Even if you use a stable sort server-side, you are not fixing the problem. As soon as a user who prefers English has a browser that sends `de-CH, en-US` you're going to be in the same boat. — FtDRbwLXw6, Aug 06 '12 at 20:57
This entire page is now obsolete. See https://wiki.php.net/rfc/stable_sorting#:~:text=A%20stable%20sort%20guarantees%20that,some%20part%20of%20that%20data. Stable sorting has been implemented 3 years ago. — mickmackusa, Apr 24 '23 at 04:16

score 1 · Accepted Answer · answered Aug 06 '12 at 20:44

You don't need to sort the array if you're only looking for the preferred language:

<?php

function findPrefferedLanguage($languages) {
  foreach ($languages as $lang => $weight) {
    if (empty($key) || ($weight > $languages[$key])) {
      $key = $lang;
    }
  }

  return $key;
}

$foo = array('es' => .6, 'en' => 1, 'fr' => 1, 'de' => .5);    

var_dump(findPrefferedLanguage($foo)); // en

Hastily tested... there's probably some edge-cases that will generate errors/warnings.

+1 Mike B, that's very clever. Don't sort if only **one** preferred language is needed. — nalply, Aug 06 '12 at 20:50

score 0 · Answer 2 · answered Aug 06 '12 at 20:33

0

Your problem isn't the unstable nature of the sort functions, but rather that you have two elements which have the same value, but you're expecting one to be sorted before the other.

If de-CH should be weighted higher than en-US, indicating that the client prefers German over English, then don't give them both values of 1.

answered Aug 06 '12 at 20:33

FtDRbwLXw6

27,774
13
70
107

That's what I'm saying.. I don't understand WHY he's sorting to begin with or where `arsort()` comes into play when parsing a string. If the order in which they're added to the array denotes the priority/weight then why did you need to sort it? – Mike B Aug 06 '12 at 20:34
I am not giving them both values of 1. The mobile phone does. – nalply Aug 06 '12 at 20:36
@nalply: Then the mobile phone doesn't prefer one over the other, and you have no problem. – FtDRbwLXw6 Aug 06 '12 at 20:37
1

@Mike: In theory there might be parameters with actual values. As a more elaborate example: `Accept-Language: en=0.50, en-GB=0.75, en-US=0.25, de-NL, de`. Where there's an implicit `=1.0` on the last two, but the more specific should take precedence. (That's another heuristic, sort country-augmented keys first..) – mario Aug 06 '12 at 20:37

score 0 · Answer 3 · answered Nov 15 '18 at 18:25

Crazy enough PHP :)

It is already mentioned in the documentation

http://php.net/manual/en/function.arsort.php

If two members compare as equal, their relative order in the sorted array is undefined.

And funny enough, it works differently in PHP 7

arsort() not stable

3 Answers3