**TimSort** is a hybrid sorting algorithm that combines **Insertion Sort** and **Merge Sort** to deliver efficient performance on real-world data. It was originally designed for Python and is now the default sorting algorithm used by Python’s `sorted()`

function and `list.sort()`

. In this post, we’ll explain how TimSort works, provide a Python implementation, and compare its performance against other sorting algorithms like Quick Sort and Merge Sort.

## What is TimSort?

**TimSort** is designed to handle real-world data efficiently by identifying already sorted subsequences, called **runs**, and merging them. This hybrid approach leverages **Insertion Sort** for small runs and **Merge Sort** to combine the runs.

### Key Points about TimSort:

**Hybrid Approach**: Combines the efficiency of Merge Sort for large datasets and the speed of Insertion Sort for smaller subarrays.**Runs**: TimSort identifies naturally occurring ordered subsequences (runs) and merges them for optimal performance.**Adaptive**: TimSort performs well on partially sorted or nearly sorted data.

## How TimSort Works

TimSort divides the dataset into small **runs** and sorts each run using Insertion Sort. It then merges these runs using Merge Sort. The algorithm dynamically adjusts the run size based on the input data.

### Steps:

- Divide the array into
**runs**(typically of size 32 or larger). - Sort each run using
**Insertion Sort**. - Merge the runs using
**Merge Sort**until the entire array is sorted.

## TimSort Pseudocode

def timsort(arr): min_run = calculate_min_run(len(arr)) # Sort individual subarrays of size min_run for start in range(0, len(arr), min_run): insertion_sort(arr, start, min((start + min_run - 1), len(arr) - 1)) # Start merging the runs size = min_run while size < len(arr): for start in range(0, len(arr), 2 * size): mid = start + size - 1 end = min((start + 2 * size - 1), len(arr) - 1) if mid < end: merge(arr, start, mid, end) size *= 2

**Insertion Sort**is used for small chunks (runs).**Merge Sort**is used to combine sorted runs into the final sorted array.

## Time Complexity of TimSort

**Best Case**: O(n) when the input data is already sorted.**Average Case**: O(n log n), as TimSort performs similarly to Merge Sort.**Worst Case**: O(n log n), since even in the worst case, TimSort guarantees efficient sorting.

## Space Complexity of TimSort

TimSort requires O(n) additional space to store temporary arrays during the merge phase.

## Python Implementation of TimSort

import timeit # Insertion Sort function to sort small runs of the array def insertion_sort(arr, left, right): # Iterate over the array from left + 1 to right for i in range(left + 1, right + 1): key = arr[i] # Current element to insert j = i - 1 # Previous element index # Move elements greater than key one position to the right while j >= left and arr[j] > key: arr[j + 1] = arr[j] j -= 1 # Insert the key element in its correct position arr[j + 1] = key # Merge function to combine two sorted subarrays into one sorted array def merge(arr, l, m, r): # Create temporary arrays to hold the left and right subarrays left = arr[l:m + 1] right = arr[m + 1:r + 1] # Indexes for left, right, and main arrays i = 0 # Initial index for left subarray j = 0 # Initial index for right subarray k = l # Initial index for main array # Merge the temporary arrays back into arr[l...r] while i < len(left) and j < len(right): if left[i] <= right[j]: arr[k] = left[i] # Copy smaller element from left subarray i += 1 else: arr[k] = right[j] # Copy smaller element from right subarray j += 1 k += 1 # Copy any remaining elements from left subarray while i < len(left): arr[k] = left[i] i += 1 k += 1 # Copy any remaining elements from right subarray while j < len(right): arr[k] = right[j] j += 1 k += 1 # Function to calculate the minimum run size for TimSort # A run is a small portion of the array to be sorted using Insertion Sort def calculate_min_run(n): r = 0 # Used to track if the array size needs to be rounded up while n >= 32: r |= n & 1 # Keep track of the least significant bit n >>= 1 # Divide the array size by 2 return n + r # Return the minimum run size (rounded up if necessary) # Main TimSort function def timsort(arr): n = len(arr) # Get the size of the array min_run = calculate_min_run(n) # Calculate the minimum run size # Sort individual subarrays (runs) of size 'min_run' using Insertion Sort for start in range(0, n, min_run): end = min(start + min_run - 1, n - 1) # Determine the end of the run insertion_sort(arr, start, end) # Sort the run using Insertion Sort # Start merging the sorted runs size = min_run while size < n: # Merge pairs of runs of size 'size' for left in range(0, n, 2 * size): mid = min(n - 1, left + size - 1) # Calculate the midpoint right = min((left + 2 * size - 1), (n - 1)) # Calculate the right end # Merge the two runs if there's something to merge if mid < right: merge(arr, left, mid, right) size *= 2 # Double the run size after each pass # Test array test_array = [34, 7, 23, 32, 5, 62, 32, 23, 6, 47, 18, 12, 39, 11, 28, 45, 19, 8, 25, 14] # Function to run TimSort on the array and measure the performance def run_timsort_performance(arr): print("Original array:", arr) # Print the original unsorted array # Make a copy of the array and run TimSort timsort_arr = arr.copy() # Measure the execution time of TimSort using timeit timsort_time = timeit.timeit(lambda: timsort(timsort_arr), number=1) # Print the sorted array and the time taken to sort print("TimSort result:", timsort_arr) print("TimSort execution time (s):", timsort_time) # Main function to run the performance test if __name__ == "__main__": run_timsort_performance(test_array) # Run TimSort on the test array

**Output:**

Original array: [34, 7, 23, 32, 5, 62, 32, 23, 6, 47, 18, 12, 39, 11, 28, 45, 19, 8, 25, 14] TimSort result: [5, 6, 7, 8, 11, 12, 14, 18, 19, 23, 23, 25, 28, 32, 32, 34, 39, 45, 47, 62] TimSort execution time (s): 1.600399991730228e-05

### Code Explanation

:`insertion_sort`

- This function sorts small subarrays (runs) of the main array using Insertion Sort, which is efficient for small datasets.

:`merge`

- Merges two sorted subarrays back into the main array. This is the merging step of TimSort, which combines sorted runs into a larger sorted array.

:`calculate_min_run`

- Calculates the minimum run size for TimSort, ensuring that the array is divided into appropriately sized subarrays for efficient sorting. A run size of around 32 is common.

:`timsort`

- This is the main TimSort function. It first divides the array into runs, sorts each run using Insertion Sort, and then merges the sorted runs using the merge function.

:`run_timsort_performance`

- This function runs TimSort on the test array, prints the original and sorted arrays, and measures the execution time using
`timeit`

.

- This function runs TimSort on the test array, prints the original and sorted arrays, and measures the execution time using
**Main Block**:- The
`if __name__ == "__main__":`

block ensures that the`run_timsort_performance`

function is executed when the script is run directly.

- The

### Walkthrough of TimSort Implementation

Let’s walk through a step-by-step example of how **TimSort** works with the array used in the code implementation array.

`[34, 7, 23, 32, 5, 62, 32, 23, 6, 47, 18, 12, 39, 11, 28, 45, 19, 8, 25, 14]`

We will assume that the minimum run size (`minRun`

) is calculated to be 5 for this example. Here’s how TimSort processes the array step-by-step:

**Initial Array**

`[34, 7, 23, 32, 5, 62, 32, 23, 6, 47, 18, 12, 39, 11, 28, 45, 19, 8, 25, 14]`

**Step 1: Divide the Array into Runs**

TimSort first breaks the array into runs, each of size `minRun = 5`

. These are the initial runs:

- Run 1:
`[34, 7, 23, 32, 5]`

- Run 2:
`[62, 32, 23, 6, 47]`

- Run 3:
`[18, 12, 39, 11, 28]`

- Run 4:
`[45, 19, 8, 25, 14]`

**Step 2: Sort Each Run Using Insertion Sort**

Now, TimSort applies **Insertion Sort** to each run to sort it individually.

#### Sorting Run 1:

- Initial Run:
`[34, 7, 23, 32, 5]`

- Sorted Run:
`[5, 7, 23, 32, 34]`

#### Sorting Run 2:

- Initial Run:
`[62, 32, 23, 6, 47]`

- Sorted Run:
`[6, 23, 32, 47, 62]`

#### Sorting Run 3:

- Initial Run:
`[18, 12, 39, 11, 28]`

- Sorted Run:
`[11, 12, 18, 28, 39]`

#### Sorting Run 4:

- Initial Run:
`[45, 19, 8, 25, 14]`

- Sorted Run:
`[8, 14, 19, 25, 45]`

After sorting, the array looks like this (with each run now sorted):

`[5, 7, 23, 32, 34] [6, 23, 32, 47, 62] [11, 12, 18, 28, 39] [8, 14, 19, 25, 45]`

**Step 3: Merge the Runs**

After sorting each run, TimSort begins merging them. It merges adjacent runs in pairs using the **Merge Sort** technique. We merge in multiple passes, doubling the size of the runs with each pass.

**First Pass (Merging Runs of Size 5)**

##### Merge Run 1 and Run 2:

- Left Run:
`[5, 7, 23, 32, 34]`

- Right Run:
`[6, 23, 32, 47, 62]`

**Merged Run**: `[5, 6, 7, 23, 23, 32, 32, 34, 47, 62]`

##### Merge Run 3 and Run 4:

- Left Run:
`[11, 12, 18, 28, 39]`

- Right Run:
`[8, 14, 19, 25, 45]`

**Merged Run**: `[8, 11, 12, 14, 18, 19, 25, 28, 39, 45]`

After the first pass, the array looks like this:

`[5, 6, 7, 23, 23, 32, 32, 34, 47, 62] [8, 11, 12, 14, 18, 19, 25, 28, 39, 45]`

**Second Pass (Merging the Final Two Runs of Size 10)**

Now, we merge the two larger runs of size 10:

##### Merge:

- Left Run:
`[5, 6, 7, 23, 23, 32, 32, 34, 47, 62]`

- Right Run:
`[8, 11, 12, 14, 18, 19, 25, 28, 39, 45]`

**Merged Array**: `[5, 6, 7, 8, 11, 12, 14, 18, 19, 23, 23, 25, 28, 32, 32, 34, 39, 45, 47, 62]`

**Final Sorted Array**

After all the runs are merged, we have the fully sorted array:

`[5, 6, 7, 8, 11, 12, 14, 18, 19, 23, 23, 25`

## TimSort vs Built-in TimSort vs Merge Sort vs Quick Sort

In Python, sorting efficiency is a critical consideration, especially for larger datasets. **TimSort** is the default sorting algorithm used by Python’s built-in `sorted()`

and `list.sort()`

functions. It is specifically designed to handle real-world data efficiently by taking advantage of runs (naturally ordered subsequences). But how does it compare with other common sorting algorithms, like **Merge Sort** and **Quick Sort**?

In this section, we will compare the performance of:

**TimSort (custom implementation)**: A hybrid sorting algorithm combining Insertion Sort and Merge Sort.**Built-in TimSort**: The built-in`sorted()`

function, which implements TimSort natively.**Merge Sort**: A stable divide-and-conquer sorting algorithm.**Quick Sort**: A fast, in-place sorting algorithm that, depending on the data, can sometimes outperform others.

We will conduct performance tests on reverse-sorted, random, and sorted arrays of sizes 1000, 5000, 10000, and 50000.

### TimSort vs Built-in TimSort vs Merge Sort vs Quick Sort: Performance Test Code

Here is the Python code for the performance test comparison:

import random import timeit # TimSort Python implementation def insertion_sort(arr, left, right): for i in range(left + 1, right + 1): key = arr[i] j = i - 1 while j >= left and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key def merge(arr, l, m, r): left = arr[l:m + 1] right = arr[m + 1:r + 1] i = 0 j = 0 k = l while i < len(left) and j < len(right): if left[i] <= right[j]: arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 k += 1 while i < len(left): arr[k] = left[i] i += 1 k += 1 while j < len(right): arr[k] = right[j] j += 1 k += 1 def calculate_min_run(n): r = 0 while n >= 32: r |= n & 1 n >>= 1 return n + r def timsort(arr): n = len(arr) min_run = calculate_min_run(n) for start in range(0, n, min_run): end = min(start + min_run - 1, n - 1) insertion_sort(arr, start, end) size = min_run while size < n: for left in range(0, n, 2 * size): mid = min(n - 1, left + size - 1) right = min((left + 2 * size - 1), (n - 1)) if mid < right: merge(arr, left, mid, right) size *= 2 # Merge Sort Python implementation def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] merge_sort(left) merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 k += 1 while i < len(left): arr[k] = left[i] i += 1 k += 1 while j < len(right): arr[k] = right[j] j += 1 k += 1 # Quick Sort Python implementation def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) # Test arrays and sizes array_sizes = [1000, 5000, 10000, 50000] # Function to generate different array types def generate_random_array(size): return [random.randint(0, 100000) for _ in range(size)] def generate_sorted_array(size): return list(range(size)) def generate_reverse_sorted_array(size): return list(range(size, 0, -1)) # Performance test function def run_performance_test(): for size in array_sizes: # Generate test arrays random_array = generate_random_array(size) sorted_array = generate_sorted_array(size) reverse_sorted_array = generate_reverse_sorted_array(size) # Measure TimSort performance timsort_time_random = timeit.timeit(lambda: timsort(random_array.copy()), number=1) timsort_time_sorted = timeit.timeit(lambda: timsort(sorted_array.copy()), number=1) timsort_time_reverse = timeit.timeit(lambda: timsort(reverse_sorted_array.copy()), number=1) # Measure built-in TimSort performance builtin_time_random = timeit.timeit(lambda: sorted(random_array.copy()), number=1) builtin_time_sorted = timeit.timeit(lambda: sorted(sorted_array.copy()), number=1) builtin_time_reverse = timeit.timeit(lambda: sorted(reverse_sorted_array.copy()), number=1) # Measure Merge Sort performance merge_time_random = timeit.timeit(lambda: merge_sort(random_array.copy()), number=1) merge_time_sorted = timeit.timeit(lambda: merge_sort(sorted_array.copy()), number=1) merge_time_reverse = timeit.timeit(lambda: merge_sort(reverse_sorted_array.copy()), number=1) # Measure Quick Sort performance quick_time_random = timeit.timeit(lambda: quick_sort(random_array.copy()), number=1) quick_time_sorted = timeit.timeit(lambda: quick_sort(sorted_array.copy()), number=1) quick_time_reverse = timeit.timeit(lambda: quick_sort(reverse_sorted_array.copy()), number=1) # Print results for current size print(f"\nArray Size: {size}") print(f"TimSort Random: {timsort_time_random}, Sorted: {timsort_time_sorted}, Reverse: {timsort_time_reverse}") print( f"Built-in TimSort Random: {builtin_time_random}, Sorted: {builtin_time_sorted}, Reverse: {builtin_time_reverse}") print(f"Merge Sort Random: {merge_time_random}, Sorted: {merge_time_sorted}, Reverse: {merge_time_reverse}") print(f"Quick Sort Random: {quick_time_random}, Sorted: {quick_time_sorted}, Reverse: {quick_time_reverse}") if __name__ == "__main__": run_performance_test()

**Output:**

Array Size: 1000 TimSort Random: 0.0016450809998787008, Sorted: 0.0007437870008288883, Reverse: 0.0022481460000562947 Built-in TimSort Random: 0.00011601100050029345, Sorted: 1.3477001630235463e-05, Reverse: 1.3111999578541145e-05 Merge Sort Random: 0.0017311960000370163, Sorted: 0.0015043709972815122, Reverse: 0.0014318670000648126 Quick Sort Random: 0.0014248229999793693, Sorted: 0.0009857160002866294, Reverse: 0.0009490580014244188 Array Size: 5000 TimSort Random: 0.009803203000046778, Sorted: 0.005523790998267941, Reverse: 0.009131142000114778 Built-in TimSort Random: 0.0005888630003028084, Sorted: 5.1107999752275646e-05, Reverse: 4.8904999857768416e-05 Merge Sort Random: 0.009586225001839921, Sorted: 0.007666212997719413, Reverse: 0.007884531001764117 Quick Sort Random: 0.007720534998952644, Sorted: 0.005034844001784222, Reverse: 0.0053981370001565665 Array Size: 10000 TimSort Random: 0.018811097001162125, Sorted: 0.011846479999803705, Reverse: 0.01917889899777947 Built-in TimSort Random: 0.0013478220025717746, Sorted: 0.00011578900011954829, Reverse: 0.000139667001349153 Merge Sort Random: 0.02028500999949756, Sorted: 0.016429164999863133, Reverse: 0.016625714000838343 Quick Sort Random: 0.01639097000224865, Sorted: 0.011415228000259958, Reverse: 0.011007416000211379 Array Size: 50000 TimSort Random: 0.11906276800073101, Sorted: 0.07946215400079382, Reverse: 0.1282699010007491 Built-in TimSort Random: 0.007791060997988097, Sorted: 0.0005915309993724804, Reverse: 0.0005682640003215056 Merge Sort Random: 0.12111129199911375, Sorted: 0.09526197599916486, Reverse: 0.09691753899824107 Quick Sort Random: 0.08853945900045801, Sorted: 0.060585850002098596, Reverse: 0.06230688100185944

Let’s put these results together in several line plots and analyse them.

# Plotting the results with specific colors for the lines: red, blue, green, and black plt.figure(figsize=(14, 10)) # Plot for Random arrays plt.subplot(3, 1, 1) plt.plot(df['Array Size'], df['TimSort Random'], label="TimSort", marker='o', color='red') plt.plot(df['Array Size'], df['Built-in TimSort Random'], label="Built-in TimSort", marker='o', color='blue') plt.plot(df['Array Size'], df['Merge Sort Random'], label="Merge Sort", marker='o', color='green') plt.plot(df['Array Size'], df['Quick Sort Random'], label="Quick Sort", marker='o', color='black') plt.title('Performance on Random Arrays') plt.xlabel('Array Size') plt.ylabel('Time (s)') plt.xscale('log') plt.legend() # Plot for Sorted arrays plt.subplot(3, 1, 2) plt.plot(df['Array Size'], df['TimSort Sorted'], label="TimSort", marker='o', color='red') plt.plot(df['Array Size'], df['Built-in TimSort Sorted'], label="Built-in TimSort", marker='o', color='blue') plt.plot(df['Array Size'], df['Merge Sort Sorted'], label="Merge Sort", marker='o', color='green') plt.plot(df['Array Size'], df['Quick Sort Sorted'], label="Quick Sort", marker='o', color='black') plt.title('Performance on Sorted Arrays') plt.xlabel('Array Size') plt.ylabel('Time (s)') plt.xscale('log') plt.legend() # Plot for Reverse Sorted arrays plt.subplot(3, 1, 3) plt.plot(df['Array Size'], df['TimSort Reverse'], label="TimSort", marker='o', color='red') plt.plot(df['Array Size'], df['Built-in TimSort Reverse'], label="Built-in TimSort", marker='o', color='blue') plt.plot(df['Array Size'], df['Merge Sort Reverse'], label="Merge Sort", marker='o', color='green') plt.plot(df['Array Size'], df['Quick Sort Reverse'], label="Quick Sort", marker='o', color='black') plt.title('Performance on Reverse Sorted Arrays') plt.xlabel('Array Size') plt.ylabel('Time (s)') plt.xscale('log') plt.legend() plt.tight_layout() plt.show()

**Analysis of the Results**

Based on the results plotted for **TimSort**, **Built-in TimSort**, **Merge Sort**, and **Quick Sort** across varying array sizes (1000, 5000, 10000, 50000) for random, sorted, and reverse-sorted arrays, here are the key insights:

#### 1. **Performance on Random Arrays**

**Built-in TimSort**consistently outperforms all other algorithms on random arrays, showing the lowest execution time for all array sizes. This is expected since Python’s built-in`sorted()`

function is highly optimized for real-world data.**Quick Sort**performs better than both**TimSort**(custom implementation) and**Merge Sort**as the array size increases, especially at sizes 10000 and 50000.**TimSort (custom)**and**Merge Sort**perform comparably for smaller arrays, but Merge Sort tends to be slightly slower for larger arrays (10000, 50000). However, the differences are not substantial.

#### 2. **Performance on Sorted Arrays**

**Built-in TimSort**performs exceptionally well, with near-instantaneous execution times, demonstrating its adaptability to already sorted data.**Quick Sort**suffers on sorted arrays because of its poor pivot selection, leading to comparatively slower execution. However, it still improves significantly for larger arrays compared to its performance on reverse-sorted arrays.**Custom TimSort**shows moderate improvement in performance over random arrays but is still slower than**Built-in TimSort**, particularly for larger arrays (50000).**Merge Sort**shows slightly better performance on sorted arrays than random or reverse-sorted data but still lags behind**TimSort**and**Quick Sort**.

#### 3. **Performance on Reverse-Sorted Arrays**

**Built-in TimSort**continues to dominate, handling reverse-sorted data with minimal overhead, as it’s designed to handle disorder efficiently.**Quick Sort**shows worse performance on reverse-sorted arrays, especially as the array size grows, due to its reliance on pivots, which leads to inefficient partitioning.**Custom TimSort**and**Merge Sort**show consistent execution times, with**Merge Sort**slightly outperforming**TimSort**in larger datasets.

**Key Takeaways**

**Built-in TimSort (Python’s**across all dataset types (random, sorted, and reverse). Its optimized implementation allows it to efficiently handle even large datasets, with near-instantaneous results on sorted and reverse-sorted data.`sorted()`

) is the clear winner**Custom TimSort**performs decently but is generally slower than**Built-in TimSort**. It performs similarly to**Merge Sort**but isn’t as optimized for sorted or reverse-sorted data.**Quick Sort**is generally faster than**TimSort**and**Merge Sort**for random datasets but struggles with sorted and reverse-sorted data due to its pivot selection strategy, leading to higher execution times.**Merge Sort**is stable across all dataset types, offering consistent performance, though it tends to be slower than both**Quick Sort**and**TimSort**for random and sorted arrays.

We have considered random, reverse-sorted and sorted, but what happens when we use partially sorted data?

First, let’s update the code with a function to generate partially sorted data and a function to run test. Then, in the main function we will add the new test to run.

import random import timeit # Function to generate a partially sorted array def generate_partially_sorted_array(size, sorted_ratio=0.8): # Create the sorted part sorted_part = list(range(int(size * sorted_ratio))) # Create the random part random_part = [random.randint(0, 100000) for _ in range(size - int(size * sorted_ratio))] # Combine the sorted and random parts return sorted_part + random_part # TimSort, Merge Sort, and Quick Sort implementations remain the same # Performance test function for partially sorted data def run_partial_sort_test(): array_sizes = [1000, 5000, 10000, 50000] for size in array_sizes: # Generate a partially sorted array partial_array = generate_partially_sorted_array(size) # Measure TimSort performance timsort_time = timeit.timeit(lambda: timsort(partial_array.copy()), number=1) # Measure built-in TimSort performance builtin_time = timeit.timeit(lambda: sorted(partial_array.copy()), number=1) # Measure Merge Sort performance merge_time = timeit.timeit(lambda: merge_sort(partial_array.copy()), number=1) # Measure Quick Sort performance quick_time = timeit.timeit(lambda: quick_sort(partial_array.copy()), number=1) # Print results for current size print(f"\nArray Size: {size}") print(f"TimSort: {timsort_time}") print(f"Built-in TimSort: {builtin_time}") print(f"Merge Sort: {merge_time}") print(f"Quick Sort: {quick_time}") if __name__ == "__main__": run_partial_sort_test()

**Remember:** we have defined TimSort, Merge Sort and Quick Sort in the earlier section.

**Output:**

Array Size: 1000 TimSort: 0.0009682749987405259 Built-in TimSort: 3.115900108241476e-05 Merge Sort: 0.0015091430032043718 Quick Sort: 0.0010818410009960644 Array Size: 5000 TimSort: 0.007126232001610333 Built-in TimSort: 0.00020182600201223977 Merge Sort: 0.009563522999087581 Quick Sort: 0.006542889001138974 Array Size: 10000 TimSort: 0.013235039998107823 Built-in TimSort: 0.0002871409997169394 Merge Sort: 0.01710491300036665 Quick Sort: 0.011640069002169184 Array Size: 50000 TimSort: 0.0786541989982652 Built-in TimSort: 0.001943560997460736 Merge Sort: 0.10525926599802915 Quick Sort: 0.07033605399919907

On a graph, the numbers look like this:

**Analysis of the Performance on Partially Sorted Data**

From the results, we can observe how **TimSort**, **Built-in TimSort**, **Merge Sort**, and **Quick Sort** perform on partially sorted arrays across different sizes.

**Performance Breakdown:**

**Built-in TimSort**:**Performance**: The built-in TimSort is**significantly faster**than the custom implementations of all other algorithms across all array sizes.**Reason**: This is because Python’s built-in`sorted()`

is highly optimized for real-world datasets, including partially sorted arrays. It identifies runs and minimizes unnecessary operations, taking full advantage of the existing order in the data.

**Custom TimSort**:**Performance**: The custom TimSort performs reasonably well but is slower than the**Built-in TimSort**and slightly slower than**Quick Sort**in most cases.**Reason**: Although TimSort is designed to handle partially sorted data, the overhead of run detection and merging operations in the custom implementation introduces more overhead compared to the highly optimized built-in version.

**Merge Sort**:**Performance**:**Merge Sort**consistently shows slower performance than both**TimSort**and**Quick Sort**for partially sorted data.**Reason**: Merge Sort does not take advantage of pre-existing order in the data. It follows a strict divide-and-conquer approach, recursively splitting the data in half and merging, which leads to redundant comparisons and operations on already sorted data.

**Quick Sort**:**Performance**:**Quick Sort**generally performs faster than**Merge Sort**and is competitive with**TimSort**.**Reason**: While Quick Sort’s performance doesn’t degrade as much on partially sorted data as it does on fully sorted or reverse-sorted data, it still doesn’t take full advantage of existing order, unlike TimSort.

**Key Takeaways**:

**Built-in TimSort**excels in handling partially sorted data, leveraging optimizations such as detecting runs and minimizing operations on sorted sequences. Its performance is much faster compared to the other algorithms, with near-instantaneous sorting for smaller arrays.**Custom TimSort**performs decently on partially sorted data but is slower than**Quick Sort**and**Built-in TimSort**due to its hybrid nature and extra overhead in managing runs and merging.**Quick Sort**continues to be competitive but doesn’t adapt to the partial order in the data as efficiently as TimSort, making it slower than both the built-in version and custom TimSort.**Merge Sort**does not optimize for pre-existing order, resulting in the slowest performance on partially sorted data.

### Why is the Built-in TimSort the Best?

#### 1. **Highly Optimized Code**:

- The built-in
`sorted()`

and`list.sort()`

functions in Python have been optimized at a low level in the C programming language. This allows the built-in TimSort to leverage highly efficient memory management, faster operations, and better CPU usage compared to custom implementations written in Python, which are generally slower due to Python’s higher-level nature and lack of the same optimization opportunities.

#### 2. **Efficient Memory Management**:

- The built-in TimSort is implemented in C, which allows it to manage memory more efficiently. It avoids unnecessary memory allocations and deallocations that might occur in a custom Python implementation. This gives the built-in version an edge in speed, especially for larger datasets.

#### 3. **Adaptive Improvements**:

- Python’s built-in TimSort includes numerous adaptive features beyond the basic algorithm, such as identifying and skipping already sorted runs. These optimizations allow it to minimize work when sorting data with patterns of partial order, making it extremely fast for real-world datasets that are often not fully randomized.
- In contrast, custom implementations may lack these sophisticated optimizations and thus perform more comparisons or unnecessary operations.

#### 4. **Better Cache Utilization**:

- The built-in TimSort is designed to efficiently use the CPU cache, which reduces cache misses and improves overall sorting speed. The custom implementation in Python does not take full advantage of cache optimization, leading to slower performance when dealing with larger datasets.

#### 5. **Low-Level Optimizations**:

- The C implementation of the built-in sort benefits from a range of low-level optimizations, such as avoiding function calls within tight loops, which makes the execution faster. Additionally, Python’s
`sorted()`

function avoids some of the overhead of interpreted Python code, further improving its performance.

#### 6. **Algorithmic Tweaks**:

- The built-in TimSort incorporates additional tweaks to improve performance in edge cases, such as choosing the right pivot size for merging runs, reducing the overhead of the merge step, and dynamically adjusting the minimum run size for certain datasets. These tweaks are often overlooked or not fully implemented in custom versions.

#### 7. **Tested and Refined**:

- Python’s built-in TimSort has undergone extensive testing, refinement, and optimization over many years. It is designed for correctness and efficiency and has been fine-tuned to work well for a wide range of input types and sizes.
- While functional, a custom implementation is unlikely to undergo the same level of testing and refinement and may, therefore, lack these optimizations and reliability.

## Advantages of TimSort

**Efficient for real-world data**: Handles partially sorted data better than traditional algorithms like Quick Sort.**Stable**: Maintains the relative order of equal elements, making it suitable for multi-criteria sorting.**Fast for Small Datasets**: Uses Insertion Sort for small runs, which is fast for small or partially sorted arrays.

## Limitations of TimSort

**Memory Usage**: Requires O(n) extra space due to its reliance on merging runs.**Not Ideal for Random Data**: While TimSort is fast, it doesn’t outperform Quick Sort on completely random data.

## When to Use TimSort

TimSort is ideal for applications where:

**Partial Ordering**: The dataset contains partially sorted or nearly sorted sequences.**Stability Matters**: Situations where maintaining the relative order of equal elements is important.**Real-World Data**: TimSort is designed to handle real-world data patterns efficiently, making it the default sorting algorithm in Python.

**Differences in Implementing TimSort in Python vs. C++**

**Performance Overhead**:**Python**: Python is an interpreted language, and its dynamic nature introduces significant overhead during execution. Each function call, memory allocation, and loop iteration is slower in Python compared to C++ due to the interpreter overhead.**C++**: In contrast, C++ is a compiled language. When implemented in C++, TimSort can use compiler optimizations like inlining, aggressive loop unrolling, and efficient memory management, making the algorithm run faster with less overhead.

**Memory Management**:**Python**: Memory management in Python is automatic (via garbage collection), which can introduce inefficiencies. The cost of memory allocations and deallocations is higher in Python, particularly for temporary arrays used during merging.**C++**: In C++, memory management can be handled more precisely using manual allocation, stack allocation, or more efficient data structures. This leads to faster and more predictable memory usage during sorting operations, especially in TimSort, where runs are continuously merged.

**Lower-level Control**:**C++**: Provides lower-level control over the hardware, such as better cache utilization, direct memory access, and fewer abstractions between the code and machine. This can significantly boost the performance of an algorithm like TimSort, which frequently interacts with memory.**Python**: Lacks this level of control, which means it cannot fully take advantage of the hardware’s capabilities, resulting in slower performance for memory-intensive operations like merging runs.

**Multi-threading and Parallelism**:**C++**: It’s easier to implement parallelism in C++ to boost performance for large datasets. TimSort in C++ could be parallelized to handle different runs or merge processes concurrently.**Python**: Python’s**Global Interpreter Lock (GIL)**limits true multi-threaded execution, making it harder to maximally exploit parallelism in a custom TimSort implementation.

## Conclusion

**TimSort** offers an adaptive, stable, efficient sorting solution for many real-world applications. It outperforms algorithms like Quick Sort and Merge Sort when handling partially sorted data. Its combination of Insertion Sort and Merge Sort ensures optimal performance across various input types. Although it may not always be the fastest for completely random data, its adaptability makes it a versatile tool for general-purpose sorting in Python.

Congratulations on reading to the end of this tutorial!

To implement TimSort in C++, go to the article How To Do TimSort in C++.

- How to do Insertion Sort in Python
- How to Do Bubble Sort in Python
- How to do Quick Sort in Python
- How to do Merge Sort in Python
- How to do Counting Sort in Python
- How to Do Radix Sort in Python
- How to Do Bucket Sort in Python
- How to Do Pigeonhole Sort in Python
- How To Do Comb Sort in Python
- How to Do Shell Sort in Python

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.