Add Tim Sort for Efficient Sorting
Closed this issue · 2 comments
Is your feature request related to a problem? Please describe.
I have observed that one of the most efficient sorting algorithm is not included in the code i.e. Tim Sort. using which we can sort the list in less time complexity as well as space complexity. The algorithm is stable as well.
Describe the solution you'd like
The idea is based on the fact that insertion sort performs well for small arrays. In Tim Sort, the input list will be divided in naturally-sorted or close-to-sorted chunks called RUNs. These runs then can be sorted using insertion sort one by one and then merge together using the combine function used in merge sort. If the size of the Array is less than run, then Array gets sorted just by using Insertion Sort. The size of the run may vary from 32 to 64 depending upon the size of the array since the merge function performs well when size subarrays are powers of 2.
Describe alternatives you've considered
The algorithm takes advantage of already-sorted elements that exist in most real-world datasets.
Additional context
Tim sort performs exceptionally well on already-sorted or close-to-sorted lists, leading to a best-case scenario of O(n). In this case, Tim sort clearly beats merge sort and matches the best-case scenario for Quicksort. But the worst case for Tim sort is also O(n log2n), which surpasses Quicksort’s O(n2).
I would like to request if this issue can be assigned to me.
Thanks!
@Abhijit2505 Can you assign me this issue?