i was solving this [problem](https://mirror.codeforces.com/contest/1980/problem/C) and i noticed that when i create a frequency array of sorted list its much faster than doing it on a unsorted list↵
↵
this is my [submession](https://mirror.codeforces.com/contest/1980/submission/264244050) with sorted, when i submit the same code without sorting it gives TL.↵
↵
then i noticed that when i loop on a sorted list is much faster than looping on a unsorted list with the same elements↵
↵
~~~~~↵
`↵
~~~~~↵
import time↵
import random↵
↵
x = []↵
counter =1↵
a = 0↵
for i in range(10**6):↵
↵
x.append(counter)↵
↵
a+=1↵
↵
if a == 2:↵
↵
a=0↵
↵
counter +=1↵
↵
x = random.sample(x,len(x))↵
↵
↵
now = time.time()↵
↵
freq1 = {}↵
↵
for i in x:↵
↵
pass↵
↵
print("done 1")↵
↵
print(time.time() — now)↵
↵
print("-----------")↵
↵
x = sorted(x)↵
↵
now = time.time()↵
↵
freq1 = {}↵
↵
for i in x:↵
↵
pass↵
↵
print("done 2")↵
↵
print(time.time() — now)↵
~~~~~↵
↵
`↵
~~~~~↵
↵
it prints↵
↵
done 1 ↵
0.16895198822021484↵
-----------↵
done 2↵
0.012014389038085938↵
-----------↵
↵
↵
the first number is the time of looping on the list while its unsorted and the second one is the time after sorting↵
↵
can any one explain why this happens
↵
this is my [submession](https://mirror.codeforces.com/contest/1980/submission/264244050) with sorted, when i submit the same code without sorting it gives TL.↵
↵
then i noticed that when i loop on a sorted list is much faster than looping on a unsorted list with the same elements↵
↵
~~~~~↵
`↵
~~~~~↵
import time↵
import random↵
↵
x = []↵
counter =1↵
a = 0↵
for i in range(10**6):↵
↵
x.append(counter)↵
↵
a+=1↵
↵
if a == 2:↵
↵
a=0↵
↵
counter +=1↵
↵
x = random.sample(x,len(x))↵
↵
↵
now = time.time()↵
↵
freq1 = {}↵
↵
for i in x:
↵
↵
print("done 1")↵
↵
print(time.time() — now)↵
↵
print("-----------")↵
↵
x = sorted(x)↵
↵
now = time.time()↵
↵
freq1 = {}↵
↵
for i in x:
↵
↵
print("done 2")↵
↵
print(time.time() — now)↵
~~~~~↵
↵
`↵
~~~~~↵
↵
it prints↵
↵
done 1 ↵
0.16895198822021484↵
-----------↵
done 2↵
0.012014389038085938↵
-----------↵
↵
↵
the first number is the time of looping on the list while its unsorted and the second one is the time after sorting↵
↵
can any one explain why this happens
