How does list.sort(key=list.count) works in Python 3.x?

Question

I would like to sort a numerical list by the frequencies of the elements. (I found several ways to do it.)

During my exploration, I tried the below example.

Question : How does list.sort(key=list.count) works? Is it possible to use list.count() during list.sort()?

I read that the key-function is evaluated for each element of the list before the sort and those values are used for the comparisons during the sort.

Also, I read somewhere that during sort() the list is kind of locked. (sorry, I can't find the reference now - I've read quite a lot of blogs and tutorials on this topic in the last few hours, Python documentation and How-To Sort included)

This is the example

### Python 3.7 ###

data = [22, 11, 33, 99, 88, 77, 22, 44, 55, 44, 66, 22]

# sort by value
data.sort()
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]

# sort by frequency, i.e. list.count()
data.sort(key=data.count)
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]
# expected >>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]
# but no change, the value-sorted list is printed

# or
data.sort(key=lambda e: data.count(e))
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]
# expected >>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]
# but no change, the value-sorted list is printed

note: no error message.

As an addition, I would like to mention that the following works as expected

max(data, key=data.count)

And, of course, this also gives the expected result

print(sorted(data, key=data.count))
>>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]

By the documentation sorted() and sort() should return the same result, don't they?

Thanks for your insights!

EDIT:

By the documentation - as I understood :

sort() takes the key-function and feeds the key-function with individual members of the list

-> the calculated results are the number of occurrences of each element (equivalent element results with equal calculated result, as their frequency is the same in the list)

: I'm not experienced to debug this deep in Python

: itself data.count() returns the appropriate list of the frequencies, that I checked
saves / caches the calculated results

: that's the foundation of its efficiency
uses the cached calculated results(!) to determine the order of the original list

-> the least frequent elements are at the front of the list, and the most frequent at he back

!!! this is not happening...
saves the list in its new order in-place

!!! ...OR this is not happening.

Additionally, as far as I understood (though not sure), somewhere during this process sort() 'locks away' the original list from other usage/access (and somewhere releases the lock - something about multi-threaded applications was in the explanation, as I recall).

IMPORTANT :

I'm not looking for a solution or code to sort the list - I'd appreciate an explanation of what's happening:

Why the result is the actual returned list and not my expectation?
In comparison, why sorted() works as expected?

user_13959505 · Answer

This is an interesting question, I do not have the full answer, as it is somewhere in the source code here: https://github.com/python/cpython/blob/master/Objects/listobject.c

However, you can have a part of the answer by using the following function as a key:

def count(e):
   print(data)
   return data.count(e)

If you do that, you will see that it only prints "[]". This means that somehow during the inplace sorting process, probably in order to avoid messing with you list, your list now points to an empty list (even though the reference itself, data, has not changed). Thus data.count(e) is always equal to 0, and your list is left unchanged.

Thus the only way to use your list during the inplace sorting process is to copy the list, you can do for instance:

data.sort(key=data.copy().count)

I will add that this does not increase very much the cost of the whole process to copy the list, as the line above is already ~~O(n² log(n))~~ O(n²) (thanks to Kelly Bundy for pointing this out) . Indeed, this is a very bad idea to call count on every element of the list. An efficient O(n log(n)) way to do that would be:

nb_occ={}
for x in data:
    nb_occ[x]=nb_occ.get(x,0)+1
data.sort(key=nb_occ.__getitem__)

EDIT: See the answer from juanpa.arrivillaga, this behaviour is actually documented in the sort method documentation.

user_5014455 · Answer

OK, according to the documentation:

CPython implementation detail: While a list is being sorted, the effect of attempting to mutate, or even inspect, the list is undefined. The C implementation of Python makes the list appear empty for the duration, and raises ValueError if it can detect that the list has been mutated during a sort.

If the bolded part is the case, then data.count will return 0 for any element, and the sort won't change the order of the list.

user_13891863 · Answer

data = [22, 11, 33, 99, 88, 77, 22, 44, 55, 44, 66, 22]
data.sort()
a,s,z,p=[],[],[],{}
for i in data:
    if i not in s:
        s.append(i)
        t=data.count(i)
        a.append(t)
for i in range(len(a)):
    p[s[i]]=a[i]
for u,m in sorted(p.items(),key=lambda x: x[1]):
    z.append(u)
print(z)

How does list.sort(key=list.count) works in Python 3.x?

EDIT:

3 Answers