Timsort
Timsort is a sorting algorithm that combines merge sort and insertion sort, and it has good efficiency in practice. Tim Peters designed this algorithm in 2002 and it is used in Python (TimSort is the default implementation of list.sort in Python). The algorithm finds sorted blocks - partitions in the data, where each partition is called a run, and then merges these runs according to certain rules. Python has been using the Timsort algorithm for sorting since version 2.3. Now, Java SE7 and Android also use the Timsort algorithm to sort arrays.
1. Operations
Most data in reality usually has some parts that are already sorted, and Timsort takes advantage of this feature. The input unit of Timsort is not individual numbers, but partitions. Each partition is called a "run" (Figure 1). For this sequence of runs, one run is taken out for merging each time. Each merge combines two runs into one run. Each run must have at least 2 elements. Timsort divides each run into ascending and descending order: if a run is in ascending order, then the next element in the run must be greater than or equal to the previous element (a[lo] <= a[lo + 1] <= a[lo + 2] <=...); if a run is in strictly descending order, that is, the previous element in the run is greater than the next element (a[lo] > a[lo + 1] > a[lo + 2] >...), the elements in the run need to be reversed (note that the descending part must be "strictly" descending to be reversed. Because an important goal of TimSort is to maintain stability. If the reversal is done in the case of >=, the algorithm will no longer be stable).
1.1 Minimum Length of Run
A run is a sorted partition. Runs may have different lengths, and Timsort selects a sorting strategy based on the length of the run. For example, if the length of a run is less than a certain value, the insertion sort algorithm will be selected for sorting. The minimum length (minrun) of a run depends on the size of the array. When the number of array elements is less than 64, the minimum length of a run is the length of the array, and Timsort uses the insertion sort algorithm for sorting. When the number of array elements is greater than or equal to 63, for larger arrays, a number, referred to as minrun, is chosen from the range 32 to 65, such that the size of the array, divided by the minimum run size, is equal to, or slightly smaller than, a power of two. The final algorithm for this simply takes the six most significant bits of the size of the array, adds one if any of the remaining bits are set, and uses that result as the minrun. This algorithm works for all cases, including the one in which the size of the array is smaller than 64.
1.2 Optimizing Run Length
Optimizing the run length means that when the length of a run is less than minrun, in order to make the length of such a run reach the minrun length, appropriate elements will be selected from the array and inserted into the run. This makes the lengths of most runs balanced, which is helpful for the subsequent merging of runs.
1.3 Merging Runs
After partitioning the runs and optimizing the run lengths, the next step is to merge the runs. The principle of merging runs is to ensure the highest efficiency in the merging technique. When the Timsort algorithm finds a run, it will put the starting position of the run in the array and the length of the run into the stack, and then decide whether to merge the run according to the previously pushed runs in the stack. Timsort will not merge non - consecutive runs in the stack (Timsort does not merge non - consecutive runs because doing this would cause the element common to all three runs to become out of order with respect to the middle run).
Timsort will merge two consecutive runs in the stack. Let X, Y, and Z represent the lengths of the three runs at the top of the stack (Figure 2). When the following two conditions are not satisfied simultaneously, the two runs X and Y will be merged until the following two conditions are satisfied simultaneously, and then the merging ends:
- X>Y+Z
- Y>Z
For example: if X<Y + Z, then X + Y are merged into a new run, and then pushed into the stack. Repeat the above steps until the two conditions are satisfied simultaneously. After the merging ends, Timsort will continue to find the next run, and then push it into the stack after finding it. Repeat the above steps, that is, every time a run is pushed into the stack, it will check whether two runs need to be merged.
1.4 Steps of Merging Runs
Merging two adjacent runs requires temporary storage space, and the size of the temporary storage space is the size of the smaller run of the two runs. The Timsort algorithm first copies the smaller run to this temporary storage space, and then uses the space originally storing the two runs to store the merged run.
The simple merging algorithm uses a simple insertion algorithm to compare elements from left to right or from right to left in turn, and then merge the two runs. To improve efficiency, Timsort uses a binary merge sort. First, use the binary search algorithm to find the insertion position, and then insert.
For example, if we want to merge two runs A and B, and A is the smaller run. Since A and B are already sorted respectively, the binary search will find where the first element of B should be inserted in A (Figure 4). Similarly, the last element of A is found where it should be inserted in B. After finding it, the elements of B after this element do not need to be compared (Figure 5). This kind of search may not be very efficient in random numbers, but it has high efficiency in other cases.
1.5 Galloping Model
It describes a merging process similar to the above runs. See the Wikipedia Galloping Model for details.
2. Performance
2.1 Core Process of Timsort
In order to reduce the backtracking of the ascending part and the performance degradation of the descending part, the TimSort algorithm partitions the input according to its ascending and descending characteristics. The input unit of sorting is not individual numbers, but blocks - partitions. Each partition is called a run. For these run sequences, one run is taken out each time and merged according to the rules. Each merge combines two runs into one run. The result of the merge is saved in the stack. The merging continues until all runs are consumed, and then the remaining runs on the stack are merged until there is only one run left. At this time, this remaining run is the sorted result.
In summary, the process of the Timsort algorithm includes:
- If the length of the array is less than a certain value, directly use the binary insertion sort algorithm.
- Find each run and push it into the stack.
- Merge runs according to the rules.
2.2 Performance Analysis
According to the theory of informatics, in the average case, comparison - based sorting cannot be faster than O(n log n). Since the Timsort algorithm takes advantage of the fact that most data in reality has some sorted areas, Timsort is faster than O(n log n). For random numbers, there are no sorted areas that can be utilized, and the time complexity of Timsort will be log(n!).
Comparison of the time complexity of Timsort with other comparison - based sorting algorithms.
Comparison of space complexities.
Explanation:
JSE 7 does not use quicksort for sorting objects because quicksort is unstable, while Timsort is stable.
The following is a passage from the Timsort implementation code in JSE7, which can well illustrate the advantages of Timsort:
A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.
Generally speaking, Timsort is a stable algorithm. When there are already sorted numbers in the array to be sorted, its time complexity will be less than n logn. Like other merge sorts, Timesrot is a stable sorting algorithm, and the worst - case time complexity is O(n log n). In the worst case, the Timsort algorithm requires temporary space of n/2, and in the best case, it only requires a very small amount of temporary storage space.
Leapcell: The Best Serverless Platform for Golang Web Hosting
Finally, I would like to recommend the best platform for deploying Golang projects: Leapcell
1. Multi - Language Support
- Develop with JavaScript, Python, Go, or Rust.
2. Deploy unlimited projects for free
- Pay only for usage — no requests, no charges.
3. Unbeatable Cost Efficiency
- Pay - as - you - go with no idle charges.
- Example: $25 supports 6.94M requests at a 60ms average response time.
4. Streamlined Developer Experience
- Intuitive UI for effortless setup.
- Fully automated CI/CD pipelines and GitOps integration.
- Real - time metrics and logging for actionable insights.
5. Effortless Scalability and High Performance
- Auto - scaling to handle high concurrency with ease.
- Zero operational overhead — just focus on building.
Explore more in the documentation!
Leapcell Twitter: https://x.com/LeapcellHQ
Top comments (0)