EDIT: What I wrote here is entirely wrong. I misread the use of 'sorted', and that colored my interpretation of the paragraph. My apologies.
"Well, this is due to something called as Branch Prediction. Branch Prediction is a strategy used in processors to decide if the branch would be taken or not."
Emphatically false. Python's sort is based on timsort. Timsort makes the observation that most real-world lists are partially sorted; either forward or reverse. This can help sorting go faster. The observed timing difference is nearly all to do with that, and not with branch prediction.
Consider the Shell sort. It's O(n*n) for an unsorted list and O(n) for a sorted list. Again, nothing to do with branch prediction and everything to do with how well the data fits the algorithm's expectations.
[+] [-] dalke|12 years ago|reply
"Well, this is due to something called as Branch Prediction. Branch Prediction is a strategy used in processors to decide if the branch would be taken or not."
Emphatically false. Python's sort is based on timsort. Timsort makes the observation that most real-world lists are partially sorted; either forward or reverse. This can help sorting go faster. The observed timing difference is nearly all to do with that, and not with branch prediction.
Consider the Shell sort. It's O(n*n) for an unsorted list and O(n) for a sorted list. Again, nothing to do with branch prediction and everything to do with how well the data fits the algorithm's expectations.
[+] [-] mayankj08|12 years ago|reply
I am just looping onto a list how is this related to complexity of sorting etc..
Sorry, but I didn't understood you properly.
[+] [-] dalke|12 years ago|reply