I've been researching python's sorting algorithm, Timsort, and know that
it's a hybrid between insertion sort (best case time complexity O(n)) and
merge sort (O(n log(n))), and has an overall time complexity of O(n
log(n)). What I'm trying to figure out is, when the list is very short,
let's say 2 or 3 units in length, does the time complexity of Timsort
become O(n)? I was thinking that the insertion-sort portion of Timsort
would be able to sort a list of length=3 (such as [8,7,9] or [9,8,7]) in
O(3) time, therefore O(n). Thoughts?
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
