Sorting is one of those basic algorithms that new programmer and CS students learn.

Maybe you already see the big-O comparison in Wikipedia, or few sites that visualize how the element in sorting move around like this.

In this notebook, we will compare the actual time comparison of different sorting algorithms.

Generating sample data

First we need to get random list of integers with different size.

import numpy as np

sizes = [2**i for i in range(4, 18)]
random_arrays = {}
for size in sizes:
    random_arrays[size] = np.random.randint(0, size, size=size)

print("Generated arrays of sizes:", list(random_arrays.keys()))

Generated arrays of sizes: [16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072]

Sorting library

We will use sortingx library to quickly get multiple different sorting algorithms.

Here we will test 6 different implementations.

import sortingx as sx
algorithms = [
    sx.bubble,
    sx.shell,
    sx.heap,
    sx.insert,
    sx.quick,
    sx.merge,
]

import time
import pandas as pd
from tqdm import tqdm

results = []
for size, arr in tqdm(random_arrays.items(), desc=f'Array sizes {size:,}'):
    for algo in algorithms:
        test_arr = arr.copy()
        start_time = time.time()
        algo(test_arr)
        end_time = time.time()
        results.append({
            'algorithm': algo.__name__,
            'array_size': size,
            'time_seconds': end_time - start_time
        })
df_results = pd.DataFrame(results)

Array sizes 131072: 100%|██████████| 14/14 [21:01<00:00, 90.09s/it] 

import matplotlib.pyplot as plt
import seaborn as sns

plt.figure(figsize=(10, 6))
sns.lineplot(data=df_results, x='array_size', y='time_seconds', hue='algorithm', marker='o')

plt.title('Sorting Algorithm Performance Comparison')
plt.xlabel('Array Size')
plt.ylabel('Time (seconds)')
plt.yscale('log')
plt.grid(True)
plt.legend(title='Algorithm')

plt.show()

And let’s do more data point but excluding the slowest algorithm.

import numpy as np
import sortingx as sx

sizes = [2**i for i in range(4, 25)]
random_arrays = {}
for size in sizes:
    random_arrays[size] = np.random.randint(0, size, size=size)
algorithms = [
    sx.shell,
    sx.heap,
    sx.quick,
    sx.merge,
]
import time
import pandas as pd
from tqdm import tqdm

results = []
for size, arr in tqdm(random_arrays.items(), desc=f'Array sizes {size:,}'):
    for algo in algorithms:
        test_arr = arr.copy()
        start_time = time.time()
        algo(test_arr)
        end_time = time.time()
        results.append({
            'algorithm': algo.__name__,
            'array_size': size,
            'time_seconds': end_time - start_time
        })
df_results = pd.DataFrame(results)
print("Generated arrays of sizes:", list(random_arrays.keys()))

Generated arrays of sizes: [16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]

import matplotlib.pyplot as plt
import seaborn as sns

plt.figure(figsize=(10, 6))
sns.lineplot(data=df_results, x='array_size', y='time_seconds', hue='algorithm', marker='o')

plt.title('Sorting Algorithm Performance Comparison')
plt.xlabel('Array Size')
plt.ylabel('Time (seconds)')
plt.yscale('log')
plt.grid(True)
plt.legend(title='Algorithm')

plt.show()

All the computation is done in my local machine, so result might varies.

Conclusion

Based on the performance comparison graph above, we can draw several key insights:

1. Algorithm Performance Tiers:

   • Bubble and Insert sort show significantly worse performance, especially for larger arrays
   • Quick, Merge, Heap and Shell sort perform notably better, clustering together at the bottom of the graph

2. Scaling Behavior:

   • All algorithms show non-linear growth as array size increases
   • Bubble sort scales the worst, with exponential growth
   • The more efficient algorithms (Quick, Merge, Heap, Shell) scale much more gracefully

3. Practical Implications:

   • For small arrays (< 20,000 elements), the difference between algorithms is less pronounced
   • For large arrays (> 60,000 elements), choosing an efficient algorithm becomes critical
   • Quick, Merge and Heap sort maintain consistent performance even at larger scales

4. Time Scale:

   • The y-axis logarithmic scale shows differences spanning several orders of magnitude
   • Bubble sort takes ~1000 seconds for large arrays
   • Efficient algorithms stay under 1 second even for the largest arrays tested

This experiment clearly demonstrates why certain sorting algorithms are preferred in practice, particularly for large datasets where performance differences become extremely significant.