# For 1 million integers:
# Option A: Python's built-in sort
sorted(python_list)  # ~150 milliseconds

# Option B: NumPy (specialized for numbers)
np.sort(numpy_array)  # ~8 milliseconds

# Result: NumPy is 19x faster for numerical data

# Bad approach: Re-sort 1,000 times
leaderboard = []
for new_score in scores:
    leaderboard.append(new_score)
    leaderboard.sort()  # Re-sorts entire list every time!

# Time: 1,000 × (sort 1,000 items) = ~10 seconds

# Better approach: Maintain sorted order
from sortedcontainers import SortedList
leaderboard = SortedList()
for new_score in scores:
    leaderboard.add(new_score)  # Inserts in correct position

# Time: ~0.01 seconds (1,000x faster!)

# Small dataset (100 items): Any approach works
sorted(small_list)  # 0.1 milliseconds - imperceptible

# Large dataset (100 million items): Choice matters
sorted(huge_list)  # ~30 seconds
# vs
polars_dataframe.sort()  # ~2 seconds (15x faster)

# E-commerce: Products sorted by price
products = db.query(Product).all()
sorted_products = sorted(products, key=lambda p: p.price)
return sorted_products[:100]  # Top 100 cheapest

# Gaming: Player scores sorted highest-first
scores = get_all_scores()
leaderboard = sorted(scores, reverse=True)
top_10 = leaderboard[:10]

# Sales: Aggregate by date (requires sorted timestamps)
sales.sort(key=lambda s: s.date)
monthly_totals = aggregate_by_month(sales)

# Find user by ID in sorted list (fast)
users.sort(key=lambda u: u.id)
target_user = binary_search(users, target_id)  # O(log n)
# vs linear search in unsorted: O(n) - 1,000x slower for large n

# Remove duplicate entries (easier when sorted)
items.sort()
unique_items = [items[0]]
for item in items[1:]:
    if item != unique_items[-1]:
        unique_items.append(item)
# vs using set (but loses order)

import numpy as np

# This uses O(n) radix sort, not O(n log n)!
arr = np.random.randint(0, 1_000_000, 10_000_000)
arr.sort(kind='stable')  # Linear time for integers

# Benchmarks show 1.5-2x faster than quicksort for large integer arrays

# Anti-pattern: O(n² log n) total cost for n insertions
for item in stream:
    data.append(item)
    data.sort()  # O(n log n) every time

# Better: O(n log n) total cost
from sortedcontainers import SortedList
data = SortedList()
for item in stream:
    data.add(item)  # O(log n) per insertion

import numpy as np

# Generate data
data = np.random.randint(0, 1_000_000, 10_000_000, dtype=np.int32)

# Fastest sort: O(n) radix sort
data.sort(kind='stable')  # In-place, linear time

# Performance: ~80ms for 10M integers

from sortedcontainers import SortedList

class Leaderboard:
    def __init__(self):
        # Key: negative score for descending order
        self.scores = SortedList(key=lambda x: -x[0])

    def add_score(self, player, score):
        self.scores.add((score, player))

    def top_10(self):
        return list(self.scores[:10])

# O(log n) per insertion, O(1) to get top-10
leaderboard = Leaderboard()
for player, score in game_results:
    leaderboard.add_score(player, score)
    print(leaderboard.top_10())

from external_sort import ExternalSortBinary
import struct

# Sort 100GB file (25 billion integers) with 4GB RAM
sorter = ExternalSortBinary(
    max_memory_mb=4000,
    record_format='i'  # 4-byte integers
)

sorter.sort_file('huge_data.bin', 'sorted_data.bin')
# Takes ~2 hours on SSD

import heapq

def top_k_from_huge_file(filename, k=100):
    """Get top k elements without loading entire file."""
    with open(filename) as f:
        # Use heap to track top k: O(n log k) time, O(k) space
        return heapq.nlargest(k, (int(line) for line in f))

# Memory: ~800 bytes for heap, not GBs for entire file
top_100 = top_k_from_huge_file('billion_numbers.txt', 100)

# Slow: 150ms for 1M elements
data = [random.randint(0, 1000000) for _ in range(1_000_000)]
data.sort()

# Fast: 15ms for 1M elements (10x faster)
data = np.random.randint(0, 1000000, 1_000_000)
data.sort()

# Terrible: O(n² log n)
for item in stream:
    data.append(item)
    data.sort()

# Good: O(n log n)
from sortedcontainers import SortedList
data = SortedList()
for item in stream:
    data.add(item)

# Wasteful: O(n log n)
sorted_data = sorted(huge_list)
top_10 = sorted_data[:10]

# Efficient: O(n + 10 log 10) ≈ O(n)
import heapq
top_10 = heapq.nlargest(10, huge_list)

# Creates copy: 2x memory usage
data = sorted(data)

# In-place: no extra memory
data.sort()

# NumPy in-place
arr.sort()  # Not: arr = np.sort(arr)

# List.sort() - in-place sorting
data = [64, 34, 25, 12, 22, 11, 90]
data.sort()
print(data)  # [11, 12, 22, 25, 34, 64, 90]

# sorted() - returns new sorted list
original = [64, 34, 25, 12, 22, 11, 90]
sorted_data = sorted(original)
print(sorted_data)  # [11, 12, 22, 25, 34, 64, 90]
print(original)     # [64, 34, 25, 12, 22, 11, 90] - unchanged

# Reverse sorting
data = [3, 1, 4, 1, 5, 9, 2, 6]
data.sort(reverse=True)
print(data)  # [9, 6, 5, 4, 3, 2, 1, 1]

# Custom key function
people = [
    {'name': 'Alice', 'age': 30},
    {'name': 'Bob', 'age': 25},
    {'name': 'Charlie', 'age': 35}
]
people.sort(key=lambda x: x['age'])
# Sorted by age: Bob(25), Alice(30), Charlie(35)

# Multiple sort keys using tuples
students = [('Alice', 'B', 85), ('Bob', 'A', 90), ('Charlie', 'B', 78)]
students.sort(key=lambda x: (x[1], -x[2]))  # Sort by grade, then score descending

# Case-insensitive sorting
words = ['banana', 'Apple', 'cherry', 'Date']
words.sort(key=str.lower)
print(words)  # ['Apple', 'banana', 'cherry', 'Date']

# Natural sorting (numbers in strings)
from functools import cmp_to_key
import re

def natural_sort_key(s):
    return [int(text) if text.isdigit() else text.lower()
            for text in re.split('([0-9]+)', s)]

files = ['file1.txt', 'file10.txt', 'file2.txt', 'file20.txt']
files.sort(key=natural_sort_key)
print(files)  # ['file1.txt', 'file2.txt', 'file10.txt', 'file20.txt']

# Use list.sort() instead of sorted() when possible (in-place, saves memory)
data.sort()  # Better
data = sorted(data)  # Creates new list

# Pre-compile key functions for repeated sorts
from operator import itemgetter
key_func = itemgetter(1)  # Faster than lambda
data.sort(key=key_func)

# Decorate-Sort-Undecorate pattern (rarely needed, built into key parameter)
# Old pattern:
decorated = [(compute_key(item), item) for item in data]
decorated.sort()
data = [item for key, item in decorated]

# Modern equivalent (preferred):
data.sort(key=compute_key)

import timeit
import random

# Generate test data
random_data = [random.randint(0, 10000) for _ in range(10000)]
sorted_data = sorted(random_data)
reversed_data = sorted_data[::-1]
partial_data = sorted_data[:5000] + random_data[5000:7500] + sorted_data[7500:]

# Benchmark
print("Random data:", timeit.timeit(lambda: sorted(random_data), number=100))
print("Sorted data:", timeit.timeit(lambda: sorted(sorted_data), number=100))
print("Reversed data:", timeit.timeit(lambda: sorted(reversed_data), number=100))
print("Partial data:", timeit.timeit(lambda: sorted(partial_data), number=100))
# Sorted and reversed will be significantly faster

import numpy as np

# np.sort() - returns sorted copy
arr = np.array([64, 34, 25, 12, 22, 11, 90])
sorted_arr = np.sort(arr)
print(sorted_arr)  # [11 12 22 25 34 64 90]
print(arr)  # [64 34 25 12 22 11 90] - original unchanged

# In-place sorting
arr.sort()  # Modifies arr directly
print(arr)  # [11 12 22 25 34 64 90]

# Specify algorithm
arr = np.array([3, 1, 4, 1, 5, 9, 2, 6])
sorted_stable = np.sort(arr, kind='stable')  # Uses radix sort for integers!
sorted_merge = np.sort(arr, kind='mergesort')
sorted_heap = np.sort(arr, kind='heapsort')

# 2D array sorting
matrix = np.array([[3, 1, 4],
                   [1, 5, 9],
                   [2, 6, 5]])

# Sort along different axes
sorted_rows = np.sort(matrix, axis=1)  # Sort each row
print(sorted_rows)
# [[1 3 4]
#  [1 5 9]
#  [2 5 6]]

sorted_cols = np.sort(matrix, axis=0)  # Sort each column
print(sorted_cols)
# [[1 1 4]
#  [2 5 5]
#  [3 6 9]]

# Flatten and sort
flat_sorted = np.sort(matrix, axis=None)
print(flat_sorted)  # [1 1 2 3 4 5 5 6 9]

# Get indices that would sort the array
arr = np.array([64, 34, 25, 12, 22, 11, 90])
indices = np.argsort(arr)
print(indices)  # [5 3 4 2 1 0 6]
print(arr[indices])  # [11 12 22 25 34 64 90] - sorted

# Sort multiple arrays based on one array's order
names = np.array(['Alice', 'Bob', 'Charlie', 'David'])
scores = np.array([85, 92, 78, 95])
indices = np.argsort(scores)[::-1]  # Descending order
print(names[indices])  # ['David' 'Bob' 'Alice' 'Charlie']
print(scores[indices])  # [95 92 85 78]

# Multi-level sorting (lexicographic)
data = np.array([(1, 3), (2, 2), (1, 1), (2, 1)],
                dtype=[('x', int), ('y', int)])
indices = np.lexsort((data['y'], data['x']))  # Sort by x, then y
print(data[indices])

# Find k smallest/largest elements efficiently
arr = np.array([64, 34, 25, 12, 22, 11, 90, 45, 33])

# Get 3 smallest elements (not fully sorted)
k = 3
partitioned = np.partition(arr, k-1)
print(partitioned[:k])  # [11 12 22] - three smallest (may not be sorted)

# Get indices of k smallest
indices = np.argpartition(arr, k-1)[:k]
top_k = arr[indices]
top_k.sort()  # Sort just the k elements
print(top_k)  # [11 12 22] - sorted

# Top 3 largest elements
k_largest_indices = np.argpartition(arr, -3)[-3:]
top_3 = arr[k_largest_indices]
top_3.sort()
print(top_3[::-1])  # [90 64 45] - descending

# Performance advantage: O(n + k log k) vs O(n log n)
# For k << n, this is much faster

import numpy as np
import time

# Large array benchmark
n = 1_000_000
arr = np.random.randint(0, 1000000, n)

# Full sort with argsort: O(n log n)
start = time.time()
indices = np.argsort(arr)[:100]  # Want 100 smallest
elapsed_argsort = time.time() - start

# Partition then sort: O(n + k log k)
start = time.time()
indices = np.argpartition(arr, 100)[:100]
smallest = arr[indices]
smallest.sort()
elapsed_partition = time.time() - start

print(f"argsort: {elapsed_argsort:.4f}s")
print(f"partition: {elapsed_partition:.4f}s")
# Partition is typically 5-10x faster for small k

# Sort complex records
employees = np.array([
    ('Alice', 25, 50000),
    ('Bob', 30, 60000),
    ('Charlie', 25, 55000),
    ('David', 30, 58000)
], dtype=[('name', 'U10'), ('age', int), ('salary', int)])

# Sort by single field
sorted_by_age = np.sort(employees, order='age')

# Multi-field sorting
sorted_emp = np.sort(employees, order=['age', 'salary'])
print(sorted_emp)
# Age 25: Alice ($50k), Charlie ($55k)
# Age 30: David ($58k), Bob ($60k)

# Ensure C-contiguous arrays for best performance
arr = np.ascontiguousarray(arr)  # Convert if needed

# Use in-place sort to save memory
arr.sort()  # Better than arr = np.sort(arr)

# For integers, request stable sort to trigger radix sort
int_arr.sort(kind='stable')  # O(n) radix sort!

# Avoid unnecessary copies
# Bad: sorted_arr = np.sort(arr.copy())
# Good: sorted_arr = np.sort(arr)  # Already makes a copy

# Use partition for top-k instead of full sort
# Bad: top_100 = np.sort(arr)[:100]  # O(n log n)
# Good:
indices = np.argpartition(arr, 100)[:100]
top_100 = np.sort(arr[indices])  # O(n + 100 log 100)

import pandas as pd
import numpy as np

# Pandas uses NumPy sorting under the hood
df = pd.DataFrame({
    'A': np.random.randint(0, 100, 1000),
    'B': np.random.randn(1000)
})

# These use NumPy's efficient sorting
df_sorted = df.sort_values('A')
df_sorted_multi = df.sort_values(['A', 'B'])

# Access underlying NumPy array for custom sorting
arr = df['A'].values
indices = np.argsort(arr)
df_custom = df.iloc[indices]

def counting_sort(arr, max_val=None):
    """
    Counting sort for non-negative integers.

    Time: O(n + k), Space: O(n + k)
    k = max_val + 1
    """
    if not arr:
        return arr

    # Determine range
    if max_val is None:
        max_val = max(arr)

    # Count occurrences
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1

    # Compute cumulative counts
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Build output array (stable)
    output = [0] * len(arr)
    for num in reversed(arr):  # Reverse to maintain stability
        output[count[num] - 1] = num
        count[num] -= 1

    return output


# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # [1, 2, 2, 3, 3, 4, 8]


# Optimized for small range
def counting_sort_inplace(arr, min_val, max_val):
    """In-place counting sort with known range."""
    k = max_val - min_val + 1
    count = [0] * k

    # Count frequencies
    for num in arr:
        count[num - min_val] += 1

    # Overwrite original array
    idx = 0
    for val in range(min_val, max_val + 1):
        arr[idx:idx + count[val - min_val]] = [val] * count[val - min_val]
        idx += count[val - min_val]

    return arr

def radix_sort(arr, base=10):
    """
    Radix sort for non-negative integers using LSD approach.

    Time: O(d(n + base)) where d is max number of digits
    Space: O(n + base)
    """
    if not arr:
        return arr

    # Find maximum number to determine number of digits
    max_num = max(arr)

    # Process each digit position
    exp = 1  # Current digit position (1, 10, 100, ...)
    while max_num // exp > 0:
        counting_sort_by_digit(arr, exp, base)
        exp *= base

    return arr


def counting_sort_by_digit(arr, exp, base):
    """Stable counting sort by specific digit position."""
    n = len(arr)
    output = [0] * n
    count = [0] * base

    # Count occurrences of digits
    for num in arr:
        digit = (num // exp) % base
        count[digit] += 1

    # Cumulative counts
    for i in range(1, base):
        count[i] += count[i - 1]

    # Build output array (reverse for stability)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % base
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1

    # Copy back to original array
    for i in range(n):
        arr[i] = output[i]


# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)  # [2, 24, 45, 66, 75, 90, 170, 802]


# Optimized for specific bit widths
def radix_sort_binary(arr):
    """Radix sort using binary digits (base 2)."""
    if not arr:
        return arr

    max_num = max(arr)
    bit = 0

    while (1 << bit) <= max_num:
        # Stable partition by bit value
        zeros = [x for x in arr if not (x >> bit) & 1]
        ones = [x for x in arr if (x >> bit) & 1]
        arr[:] = zeros + ones
        bit += 1

    return arr

def radix_sort_strings(strings, max_len=None):
    """
    Radix sort for fixed-length or similar-length strings.
    Sorts from rightmost character to leftmost (LSD).
    """
    if not strings:
        return strings

    # Determine maximum length
    if max_len is None:
        max_len = max(len(s) for s in strings)

    # Pad strings to same length
    strings = [s.ljust(max_len) for s in strings]

    # Sort by each character position (right to left)
    for pos in range(max_len - 1, -1, -1):
        # Counting sort by character at position pos
        buckets = [[] for _ in range(256)]  # ASCII range

        for s in strings:
            char_code = ord(s[pos])
            buckets[char_code].append(s)

        # Flatten buckets
        strings = [s for bucket in buckets for s in bucket]

    # Remove padding
    return [s.rstrip() for s in strings]


# Example
words = ['apple', 'application', 'apply', 'ape', 'apricot']
sorted_words = radix_sort_strings(words)
print(sorted_words)

import time
import random
from statistics import mean

def benchmark_sorts(n, k):
    """Compare counting sort, radix sort, and Python's sort."""

    # Generate data: n numbers in range [0, k)
    data = [random.randint(0, k-1) for _ in range(n)]

    # Python's Timsort
    test_data = data.copy()
    start = time.time()
    test_data.sort()
    timsort_time = time.time() - start

    # Counting sort
    test_data = data.copy()
    start = time.time()
    result = counting_sort(test_data, k-1)
    counting_time = time.time() - start

    # Radix sort
    test_data = data.copy()
    start = time.time()
    radix_sort(test_data)
    radix_time = time.time() - start

    print(f"n={n:,}, k={k:,}")
    print(f"  Timsort:      {timsort_time:.4f}s")
    print(f"  Counting sort: {counting_time:.4f}s ({timsort_time/counting_time:.1f}x)")
    print(f"  Radix sort:    {radix_time:.4f}s ({timsort_time/radix_time:.1f}x)")
    print()

# Best case for counting sort: k is small
benchmark_sorts(1_000_000, 1_000)

# Best case for radix sort: fixed-width integers
benchmark_sorts(1_000_000, 1_000_000_000)

# Worst case: k is very large
benchmark_sorts(100_000, 100_000_000)

# Example: Sort student grades (0-100)
grades = [85, 92, 78, 85, 95, 88, 92, 85]
sorted_grades = counting_sort(grades, max_val=100)
# O(n + 100) = O(n) time

# Example: Sort 32-bit unsigned integers
import numpy as np

def radix_sort_numpy(arr):
    """Leverage NumPy for efficient radix sort."""
    # NumPy's stable sort uses radix sort for integers!
    return np.sort(arr, kind='stable')

# This is O(n) for integers
large_array = np.random.randint(0, 2**32, 1_000_000, dtype=np.uint32)
sorted_array = radix_sort_numpy(large_array)

import numpy as np

# NumPy automatically uses radix sort for integers with stable sort!
arr = np.random.randint(0, 1_000_000, 1_000_000)

# This uses O(n) radix sort internally
sorted_arr = np.sort(arr, kind='stable')

# Verify it's fast
import time
start = time.time()
np.sort(arr, kind='stable')
stable_time = time.time() - start

start = time.time()
np.sort(arr, kind='quicksort')
quick_time = time.time() - start

print(f"Stable (radix): {stable_time:.4f}s")
print(f"Quicksort: {quick_time:.4f}s")
# Radix sort is typically 1.5-2x faster for integers

# Decision tree for sorting integers

def choose_sort(data, data_range=None):
    """Recommend sorting algorithm based on data characteristics."""
    n = len(data)

    if data_range is None:
        data_range = max(data) - min(data) + 1

    # Use counting sort if range is small
    if data_range <= 10 * n:
        return "counting_sort"

    # Use radix sort for fixed-width integers
    if all(isinstance(x, int) and x < 2**32 for x in data):
        return "radix_sort (or NumPy stable sort)"

    # Default to Timsort
    return "built-in sort()"

# Examples
print(choose_sort([1, 2, 3, 4, 5] * 1000))  # counting_sort
print(choose_sort(list(range(1_000_000))))  # radix_sort
print(choose_sort([random.random() for _ in range(1000)]))  # built-in sort()

import multiprocessing as mp
from multiprocessing import Pool
import numpy as np

def parallel_sort_chunks(data, n_jobs=None):
    """
    Divide-and-conquer parallel sort.

    Time: O(n log n / p + n) - sort chunks + merge
    Works well for n > 1M elements
    """
    if n_jobs is None:
        n_jobs = mp.cpu_count()

    # Split data into chunks
    chunk_size = len(data) // n_jobs
    chunks = [data[i:i + chunk_size]
              for i in range(0, len(data), chunk_size)]

    # Sort chunks in parallel
    with Pool(n_jobs) as pool:
        sorted_chunks = pool.map(sorted, chunks)

    # Merge sorted chunks
    return merge_sorted_chunks(sorted_chunks)


def merge_sorted_chunks(chunks):
    """Merge multiple sorted chunks using heap."""
    import heapq

    # Use heap to efficiently merge k sorted lists
    result = []
    heap = []

    # Initialize heap with first element from each chunk
    for i, chunk in enumerate(chunks):
        if chunk:
            heapq.heappush(heap, (chunk[0], i, 0))

    # Extract minimum and add next element from same chunk
    while heap:
        val, chunk_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        if elem_idx + 1 < len(chunks[chunk_idx]):
            next_val = chunks[chunk_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, chunk_idx, elem_idx + 1))

    return result


# Example usage
data = list(np.random.randint(0, 1_000_000, 5_000_000))
sorted_data = parallel_sort_chunks(data, n_jobs=8)

from joblib import Parallel, delayed
import numpy as np

def parallel_sort_joblib(data, n_jobs=-1, backend='loky'):
    """
    Parallel sort using joblib with optimized memory handling.

    Joblib advantages:
    - Automatic memmap for large arrays
    - Better serialization
    - Progress tracking
    - Multiple backends
    """
    chunk_size = len(data) // (n_jobs if n_jobs > 0 else mp.cpu_count())

    # Create chunks
    chunks = [data[i:i + chunk_size]
              for i in range(0, len(data), chunk_size)]

    # Sort in parallel with joblib
    sorted_chunks = Parallel(n_jobs=n_jobs, backend=backend)(
        delayed(sorted)(chunk) for chunk in chunks
    )

    return merge_sorted_chunks(sorted_chunks)


# For NumPy arrays - better performance
def parallel_sort_numpy(arr, n_jobs=-1):
    """
    Parallel sort for NumPy arrays using joblib.
    Leverages memmap for large arrays.
    """
    from joblib import Parallel, delayed

    n_cores = mp.cpu_count() if n_jobs == -1 else n_jobs
    chunk_size = len(arr) // n_cores

    # Split array into chunks
    chunks = [arr[i:i + chunk_size]
              for i in range(0, len(arr), chunk_size)]

    # Sort chunks in parallel (joblib uses memmap automatically for large arrays)
    sorted_chunks = Parallel(n_jobs=n_jobs, verbose=0)(
        delayed(np.sort)(chunk) for chunk in chunks
    )

    # Merge using NumPy's efficient concatenate + sort
    # For large arrays, might want iterative merge
    merged = np.concatenate(sorted_chunks)
    merged.sort()  # Final sort is fast on partially sorted data

    return merged


# Example
arr = np.random.randint(0, 1_000_000, 10_000_000)
sorted_arr = parallel_sort_numpy(arr, n_jobs=8)

def parallel_merge_sort(data, n_jobs=None, threshold=10000):
    """
    True parallel merge sort with recursive parallelization.
    Only worth it for very large datasets.
    """
    if n_jobs is None:
        n_jobs = mp.cpu_count()

    def _parallel_merge_sort(arr, depth=0):
        # Base case: use sequential sort for small arrays
        if len(arr) <= threshold or depth >= 3:
            return sorted(arr)

        # Split in half
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        # Sort halves in parallel
        with Pool(2) as pool:
            left_sorted, right_sorted = pool.starmap(
                _parallel_merge_sort,
                [(left, depth + 1), (right, depth + 1)]
            )

        # Merge
        return merge_two_sorted(left_sorted, right_sorted)

    return _parallel_merge_sort(data)


def merge_two_sorted(left, right):
    """Efficiently merge two sorted lists."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

from multiprocessing import shared_memory, Pool
import numpy as np

def parallel_sort_shared_memory(arr, n_jobs=None):
    """
    Parallel sort using shared memory to avoid copying.
    Most efficient for very large NumPy arrays.
    """
    if n_jobs is None:
        n_jobs = mp.cpu_count()

    # Create shared memory
    shm = shared_memory.SharedMemory(create=True, size=arr.nbytes)
    shared_arr = np.ndarray(arr.shape, dtype=arr.dtype, buffer=shm.buf)
    shared_arr[:] = arr[:]

    # Calculate chunk boundaries
    chunk_size = len(arr) // n_jobs
    ranges = [(i * chunk_size, min((i + 1) * chunk_size, len(arr)))
              for i in range(n_jobs)]

    # Sort chunks in place
    def sort_chunk(shm_name, shape, dtype, start, end):
        existing_shm = shared_memory.SharedMemory(name=shm_name)
        shared_array = np.ndarray(shape, dtype=dtype, buffer=existing_shm.buf)
        shared_array[start:end].sort()
        existing_shm.close()

    with Pool(n_jobs) as pool:
        pool.starmap(
            sort_chunk,
            [(shm.name, arr.shape, arr.dtype, start, end)
             for start, end in ranges]
        )

    # Merge sorted chunks (in place if possible)
    result = shared_arr.copy()
    shm.close()
    shm.unlink()

    # Final merge (could also be parallelized)
    return np.sort(result)  # Timsort is fast on partially sorted data


# Example
large_array = np.random.randint(0, 1_000_000, 20_000_000)
sorted_array = parallel_sort_shared_memory(large_array, n_jobs=8)

import time
from statistics import mean

def benchmark_parallel_sorts(n=10_000_000):
    """Compare serial vs parallel sorting performance."""

    # Generate test data
    data = list(np.random.randint(0, 1_000_000, n))
    arr = np.array(data)

    print(f"Sorting {n:,} elements")
    print("-" * 50)

    # Serial sort (Python)
    test_data = data.copy()
    start = time.time()
    test_data.sort()
    serial_time = time.time() - start
    print(f"Serial Python sort:     {serial_time:.3f}s")

    # Serial NumPy sort
    test_arr = arr.copy()
    start = time.time()
    np.sort(test_arr)
    numpy_time = time.time() - start
    print(f"Serial NumPy sort:      {numpy_time:.3f}s ({serial_time/numpy_time:.1f}x)")

    # Parallel sort (multiprocessing)
    test_data = data.copy()
    start = time.time()
    parallel_sort_chunks(test_data, n_jobs=8)
    parallel_time = time.time() - start
    print(f"Parallel MP sort (8j):  {parallel_time:.3f}s ({serial_time/parallel_time:.1f}x)")

    # Parallel sort (joblib)
    test_data = data.copy()
    start = time.time()
    parallel_sort_joblib(test_data, n_jobs=8)
    joblib_time = time.time() - start
    print(f"Parallel joblib (8j):   {joblib_time:.3f}s ({serial_time/joblib_time:.1f}x)")

    # Parallel NumPy
    test_arr = arr.copy()
    start = time.time()
    parallel_sort_numpy(test_arr, n_jobs=8)
    parallel_numpy_time = time.time() - start
    print(f"Parallel NumPy (8j):    {parallel_numpy_time:.3f}s ({numpy_time/parallel_numpy_time:.1f}x)")

# Run benchmark
benchmark_parallel_sorts()

# Typical results on 8-core CPU:
# Serial Python sort:     2.500s
# Serial NumPy sort:      0.180s (13.9x)
# Parallel MP sort (8j):  0.850s (2.9x)
# Parallel joblib (8j):   0.780s (3.2x)
# Parallel NumPy (8j):    0.090s (2.0x faster than serial NumPy)

# 1. Use NumPy arrays instead of lists
# Bad: parallel_sort_chunks(list(range(10_000_000)))
# Good: parallel_sort_numpy(np.arange(10_000_000))

# 2. Tune number of jobs
n_jobs = min(mp.cpu_count(), len(data) // 100_000)  # Don't over-parallelize

# 3. Use appropriate backend in joblib
# For CPU-bound: 'loky' or 'multiprocessing'
# For I/O-bound: 'threading'
Parallel(n_jobs=8, backend='loky')

# 4. Consider chunk size
# Too small: high overhead
# Too large: poor load balancing
optimal_chunk_size = len(data) // (n_jobs * 2)

# 5. Profile before optimizing
import cProfile
cProfile.run('parallel_sort_numpy(arr, n_jobs=8)')

# Pattern 1: Parallel preprocessing + single-threaded sort
from joblib import Parallel, delayed

def process_and_sort(data, n_jobs=-1):
    """Process in parallel, then sort (if result fits in memory)."""

    # Parallel processing
    processed = Parallel(n_jobs=n_jobs)(
        delayed(expensive_transform)(item) for item in data
    )

    # Single-threaded sort (often faster for moderate sizes)
    return sorted(processed, key=lambda x: x.score)


# Pattern 2: Sorting within parallel pipeline
def parallel_pipeline(datasets):
    """Sort each dataset in parallel pipeline."""

    def process_dataset(data):
        # Each worker sorts its own data
        data = sorted(data, key=lambda x: x.timestamp)
        return analyze(data)

    results = Parallel(n_jobs=-1)(
        delayed(process_dataset)(dataset) for dataset in datasets
    )

    return results

def smart_sort(data, force_parallel=False):
    """
    Intelligently choose sorting strategy based on data characteristics.
    """
    n = len(data)

    # Small data: use built-in sort
    if n < 1_000_000 and not force_parallel:
        if isinstance(data, np.ndarray):
            return np.sort(data)
        return sorted(data)

    # Large NumPy arrays: parallel NumPy sort
    if isinstance(data, np.ndarray) and n > 5_000_000:
        return parallel_sort_numpy(data, n_jobs=-1)

    # Large lists: joblib parallel sort
    if n > 5_000_000:
        return parallel_sort_joblib(data, n_jobs=-1)

    # Default: built-in sort is well-optimized
    if isinstance(data, np.ndarray):
        return np.sort(data)
    return sorted(data)

import heapq
import os
import tempfile
from typing import Iterator, List
import pickle

class ExternalSort:
    """
    External merge sort for large files that don't fit in memory.

    Features:
    - Configurable memory limit
    - Efficient k-way merge with heap
    - Automatic cleanup of temporary files
    """

    def __init__(self, max_memory_mb=100):
        self.max_memory = max_memory_mb * 1024 * 1024  # Convert to bytes
        self.temp_files = []

    def sort_file(self, input_file, output_file, key=None):
        """
        Sort large file using external merge sort.

        Args:
            input_file: Path to input file (one item per line)
            output_file: Path to output file
            key: Optional key function for sorting
        """
        # Phase 1: Create sorted runs
        self._create_sorted_runs(input_file, key)

        # Phase 2: Merge runs
        self._merge_runs(output_file, key)

        # Cleanup
        self._cleanup()

    def _create_sorted_runs(self, input_file, key=None):
        """Read chunks, sort, write to temp files."""
        chunk = []
        chunk_size = 0
        run_number = 0

        with open(input_file, 'r') as f:
            for line in f:
                line = line.rstrip('\n')
                line_size = len(line.encode('utf-8'))

                # Check if adding this line exceeds memory limit
                if chunk_size + line_size > self.max_memory and chunk:
                    # Write current chunk
                    self._write_sorted_chunk(chunk, run_number, key)
                    chunk = []
                    chunk_size = 0
                    run_number += 1

                chunk.append(line)
                chunk_size += line_size

            # Write final chunk
            if chunk:
                self._write_sorted_chunk(chunk, run_number, key)

    def _write_sorted_chunk(self, chunk, run_number, key=None):
        """Sort chunk and write to temporary file."""
        chunk.sort(key=key)

        temp_file = tempfile.NamedTemporaryFile(
            mode='w',
            delete=False,
            prefix=f'run_{run_number}_'
        )
        self.temp_files.append(temp_file.name)

        for item in chunk:
            temp_file.write(f"{item}\n")

        temp_file.close()

    def _merge_runs(self, output_file, key=None):
        """K-way merge of all sorted runs."""
        # Open all run files
        file_handles = [open(f, 'r') for f in self.temp_files]

        # Initialize heap with first line from each file
        heap = []
        for i, fh in enumerate(file_handles):
            line = fh.readline().rstrip('\n')
            if line:
                sort_key = key(line) if key else line
                heapq.heappush(heap, (sort_key, i, line))

        # Merge using heap
        with open(output_file, 'w') as out:
            while heap:
                sort_key, file_idx, line = heapq.heappop(heap)
                out.write(f"{line}\n")

                # Read next line from same file
                next_line = file_handles[file_idx].readline().rstrip('\n')
                if next_line:
                    next_key = key(next_line) if key else next_line
                    heapq.heappush(heap, (next_key, file_idx, next_line))

        # Close all files
        for fh in file_handles:
            fh.close()

    def _cleanup(self):
        """Remove temporary files."""
        for temp_file in self.temp_files:
            try:
                os.remove(temp_file)
            except OSError:
                pass
        self.temp_files = []


# Example usage
def example_basic():
    # Create large test file
    with open('large_data.txt', 'w') as f:
        for i in range(10_000_000, 0, -1):
            f.write(f"{i}\n")

    # Sort with 100MB memory limit
    sorter = ExternalSort(max_memory_mb=100)
    sorter.sort_file('large_data.txt', 'sorted_data.txt')

    # Verify first few lines
    with open('sorted_data.txt', 'r') as f:
        for i in range(10):
            print(f.readline().rstrip())

import struct
import heapq
import tempfile
import os

class ExternalSortBinary:
    """
    Optimized external sort for binary numerical data.
    Much faster than text-based sorting due to:
    - Fixed record size
    - No parsing overhead
    - Efficient buffering
    """

    def __init__(self, max_memory_mb=100, record_format='i'):
        """
        Args:
            max_memory_mb: Memory limit in MB
            record_format: struct format ('i' for int, 'f' for float, etc.)
        """
        self.max_memory = max_memory_mb * 1024 * 1024
        self.record_format = record_format
        self.record_size = struct.calcsize(record_format)
        self.temp_files = []

    def sort_file(self, input_file, output_file):
        """Sort binary file of fixed-size records."""
        # Phase 1: Create sorted runs
        self._create_runs(input_file)

        # Phase 2: Merge runs
        self._merge_runs(output_file)

        # Cleanup
        self._cleanup()

    def _create_runs(self, input_file):
        """Create sorted runs from input file."""
        chunk_size = self.max_memory // self.record_size

        with open(input_file, 'rb') as f:
            run_number = 0

            while True:
                # Read chunk
                chunk_bytes = f.read(chunk_size * self.record_size)
                if not chunk_bytes:
                    break

                # Unpack to list
                n_records = len(chunk_bytes) // self.record_size
                chunk = list(struct.unpack(
                    f'{n_records}{self.record_format}',
                    chunk_bytes
                ))

                # Sort
                chunk.sort()

                # Write to temp file
                temp_file = tempfile.NamedTemporaryFile(
                    mode='wb',
                    delete=False,
                    prefix=f'run_{run_number}_'
                )
                self.temp_files.append(temp_file.name)

                # Pack and write
                packed = struct.pack(
                    f'{len(chunk)}{self.record_format}',
                    *chunk
                )
                temp_file.write(packed)
                temp_file.close()

                run_number += 1

    def _merge_runs(self, output_file):
        """K-way merge of binary runs."""
        # Open all runs
        file_handles = [open(f, 'rb') for f in self.temp_files]

        # Buffer size per file
        buffer_size = (self.max_memory // len(file_handles)) // self.record_size

        # Initialize heap
        heap = []
        buffers = [[] for _ in file_handles]

        # Fill initial buffers
        for i, fh in enumerate(file_handles):
            self._fill_buffer(fh, buffers[i], buffer_size)
            if buffers[i]:
                value = buffers[i].pop(0)
                heapq.heappush(heap, (value, i))

        # Merge
        with open(output_file, 'wb') as out:
            output_buffer = []

            while heap:
                value, file_idx = heapq.heappop(heap)
                output_buffer.append(value)

                # Flush output buffer if full
                if len(output_buffer) >= buffer_size:
                    self._flush_buffer(out, output_buffer)

                # Refill input buffer if needed
                if not buffers[file_idx]:
                    self._fill_buffer(
                        file_handles[file_idx],
                        buffers[file_idx],
                        buffer_size
                    )

                # Add next value from same file
                if buffers[file_idx]:
                    next_value = buffers[file_idx].pop(0)
                    heapq.heappush(heap, (next_value, file_idx))

            # Flush remaining output
            if output_buffer:
                self._flush_buffer(out, output_buffer)

        # Close files
        for fh in file_handles:
            fh.close()

    def _fill_buffer(self, file_handle, buffer, size):
        """Read records from file into buffer."""
        buffer.clear()
        chunk_bytes = file_handle.read(size * self.record_size)
        if chunk_bytes:
            n_records = len(chunk_bytes) // self.record_size
            buffer.extend(struct.unpack(
                f'{n_records}{self.record_format}',
                chunk_bytes
            ))

    def _flush_buffer(self, file_handle, buffer):
        """Write buffer to file and clear."""
        packed = struct.pack(
            f'{len(buffer)}{self.record_format}',
            *buffer
        )
        file_handle.write(packed)
        buffer.clear()

    def _cleanup(self):
        """Remove temporary files."""
        for temp_file in self.temp_files:
            try:
                os.remove(temp_file)
            except OSError:
                pass


# Example: Sort 1 billion integers (4GB file)
def example_binary():
    import random

    # Create large binary file
    print("Creating test file...")
    with open('large_numbers.bin', 'wb') as f:
        for _ in range(100_000_000):  # 100M integers = 400MB
            num = random.randint(0, 1_000_000_000)
            f.write(struct.pack('i', num))

    # Sort with 100MB memory
    print("Sorting...")
    import time
    start = time.time()

    sorter = ExternalSortBinary(max_memory_mb=100, record_format='i')
    sorter.sort_file('large_numbers.bin', 'sorted_numbers.bin')

    print(f"Sorted in {time.time() - start:.2f} seconds")

    # Verify
    with open('sorted_numbers.bin', 'rb') as f:
        for i in range(10):
            num = struct.unpack('i', f.read(4))[0]
            print(num)

import heapq
import csv
import tempfile
import os

def external_sort_csv(input_csv, output_csv, sort_column, max_memory_mb=100):
    """
    External sort for CSV files by specific column.

    Useful for log files, database dumps, etc.
    """
    max_rows = (max_memory_mb * 1024 * 1024) // 1000  # Rough estimate

    temp_files = []

    # Phase 1: Create sorted runs
    with open(input_csv, 'r', newline='') as f:
        reader = csv.DictReader(f)
        chunk = []

        for row in reader:
            chunk.append(row)

            if len(chunk) >= max_rows:
                # Sort chunk
                chunk.sort(key=lambda x: x[sort_column])

                # Write to temp file
                temp_file = tempfile.NamedTemporaryFile(
                    mode='w',
                    delete=False,
                    newline='',
                    suffix='.csv'
                )
                temp_files.append(temp_file.name)

                writer = csv.DictWriter(temp_file, fieldnames=reader.fieldnames)
                writer.writeheader()
                writer.writerows(chunk)
                temp_file.close()

                chunk = []

        # Write final chunk
        if chunk:
            chunk.sort(key=lambda x: x[sort_column])
            temp_file = tempfile.NamedTemporaryFile(
                mode='w',
                delete=False,
                newline='',
                suffix='.csv'
            )
            temp_files.append(temp_file.name)
            writer = csv.DictWriter(temp_file, fieldnames=reader.fieldnames)
            writer.writeheader()
            writer.writerows(chunk)
            temp_file.close()

    # Phase 2: K-way merge
    readers = [csv.DictReader(open(f, 'r', newline='')) for f in temp_files]
    with open(output_csv, 'w', newline='') as out:
        writer = csv.DictWriter(out, fieldnames=reader.fieldnames)
        writer.writeheader()

        # Initialize heap
        heap = []
        for i, r in enumerate(readers):
            try:
                row = next(r)
                heapq.heappush(heap, (row[sort_column], i, row))
            except StopIteration:
                pass

        # Merge
        while heap:
            _, i, row = heapq.heappop(heap)
            writer.writerow(row)

            try:
                next_row = next(readers[i])
                heapq.heappush(heap, (next_row[sort_column], i, next_row))
            except StopIteration:
                pass

    # Cleanup
    for f in temp_files:
        os.remove(f)

# 1. Maximize chunk size (use most of available RAM)
import psutil
available_mb = psutil.virtual_memory().available // (1024 * 1024)
chunk_size_mb = int(available_mb * 0.8)  # Use 80% of available

# 2. Use SSD for temporary files
import tempfile
tempfile.tempdir = '/path/to/ssd'  # Set to fast SSD

# 3. Optimize number of runs (larger chunks = fewer runs)
# Fewer runs = faster merge
# Formula: num_runs = ceil(file_size / chunk_size)

# 4. Use binary format when possible (10x faster than text)
# Bad: text CSV with parsing
# Good: binary struct format or pickle

# 5. Buffer I/O operations
# Use large read/write buffers (1-10MB)
with open('file', 'rb', buffering=10*1024*1024) as f:
    pass

# 6. Consider compression for I/O-bound scenarios
import gzip
# Compressed I/O can be faster if CPU > disk speed

def choose_sorting_strategy(file_size_gb, available_ram_gb):
    """Recommend sorting strategy based on resources."""

    if file_size_gb <= available_ram_gb * 0.5:
        return "in_memory_sort"  # Load entire file into RAM

    if file_size_gb <= available_ram_gb * 2:
        return "memory_mapped_sort"  # Use mmap

    if file_size_gb > available_ram_gb * 10:
        return "distributed_sort"  # Consider Spark/Dask

    return "external_merge_sort"  # Classic external sort


# Example decisions
print(choose_sorting_strategy(file_size_gb=2, available_ram_gb=8))
# Output: "in_memory_sort"

print(choose_sorting_strategy(file_size_gb=50, available_ram_gb=4))
# Output: "external_merge_sort"

from sortedcontainers import SortedList

# Create sorted list
sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6])
print(sl)  # SortedList([1, 1, 2, 3, 4, 5, 6, 9])

# Add elements (maintains sorted order automatically)
sl.add(7)
print(sl)  # SortedList([1, 1, 2, 3, 4, 5, 6, 7, 9])

# Add multiple elements efficiently
sl.update([0, 10, 5])
print(sl)  # SortedList([0, 1, 1, 2, 3, 4, 5, 5, 6, 7, 9, 10])

# Remove elements
sl.remove(5)  # Removes first occurrence
print(sl)  # SortedList([0, 1, 1, 2, 3, 4, 5, 6, 7, 9, 10])

# Discard (doesn't raise error if not found)
sl.discard(100)  # No error

# Pop elements
last = sl.pop()  # Remove and return last element
first = sl.pop(0)  # Remove and return first element

# Index access (O(1))
print(sl[0])  # First element
print(sl[-1])  # Last element
print(sl[2:5])  # Slicing works

# Binary search
index = sl.bisect_left(5)  # Find insertion point
index = sl.bisect_right(5)  # Find insertion point (after existing)

# Count occurrences
count = sl.count(1)  # Count how many 1's

from sortedcontainers import SortedList

# Custom key function
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"Person({self.name}, {self.age})"

# Sort by age
people = SortedList(key=lambda p: p.age)
people.add(Person('Alice', 30))
people.add(Person('Bob', 25))
people.add(Person('Charlie', 35))
print(people)
# [Person(Bob, 25), Person(Alice, 30), Person(Charlie, 35)]

# Range queries (very efficient)
sl = SortedList(range(1000))

# Find all elements in range [100, 200)
start_idx = sl.bisect_left(100)
end_idx = sl.bisect_left(200)
elements_in_range = sl[start_idx:end_idx]

# IRange - iterate over range efficiently
for item in sl.irange(100, 200):  # Exclusive end
    process(item)

# IRange with min/max parameters
for item in sl.irange(minimum=100, maximum=200, inclusive=(True, False)):
    process(item)

from sortedcontainers import SortedDict

# Create sorted dictionary (keys are sorted)
sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
print(sd)  # SortedDict({'a': 1, 'b': 2, 'c': 3})

# Add items (maintains key order)
sd['d'] = 4
sd['aa'] = 1.5

# Iterate in sorted key order
for key, value in sd.items():
    print(f"{key}: {value}")

# Access by index
first_key = sd.keys()[0]  # 'a'
first_value = sd.values()[0]  # 1

# Range queries on keys
sd = SortedDict({i: i**2 for i in range(100)})

# Get all items with keys in range [25, 50)
start_idx = sd.bisect_left(25)
end_idx = sd.bisect_left(50)
range_items = {sd.keys()[i]: sd.values()[i]
               for i in range(start_idx, end_idx)}

# IRange on keys
for key in sd.irange(25, 50):
    print(f"{key}: {sd[key]}")

from sortedcontainers import SortedSet

# Create sorted set
ss = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])
print(ss)  # SortedSet([1, 2, 3, 4, 5, 6, 9])

# Set operations (all maintain sorted order)
ss1 = SortedSet([1, 2, 3, 4, 5])
ss2 = SortedSet([4, 5, 6, 7, 8])

union = ss1 | ss2  # SortedSet([1, 2, 3, 4, 5, 6, 7, 8])
intersection = ss1 & ss2  # SortedSet([4, 5])
difference = ss1 - ss2  # SortedSet([1, 2, 3])
symmetric_diff = ss1 ^ ss2  # SortedSet([1, 2, 3, 6, 7, 8])

# Range queries
ss = SortedSet(range(100))
subset = ss.irange(25, 50)  # Elements in [25, 50)

# Index access
print(ss[0])  # Smallest element
print(ss[-1])  # Largest element

from sortedcontainers import SortedList

class RunningMedian:
    """
    Efficiently maintain median of streaming data.
    O(log n) insertion vs O(n log n) with repeated sorting.
    """

    def __init__(self):
        self.sorted_data = SortedList()

    def add(self, num):
        """Add number and return current median. O(log n)"""
        self.sorted_data.add(num)
        return self.get_median()

    def get_median(self):
        """Get current median. O(1)"""
        n = len(self.sorted_data)
        if n == 0:
            return None

        if n % 2 == 1:
            return self.sorted_data[n // 2]
        else:
            return (self.sorted_data[n // 2 - 1] +
                    self.sorted_data[n // 2]) / 2


# Usage
rm = RunningMedian()
for num in [5, 2, 8, 1, 9]:
    median = rm.add(num)
    print(f"Added {num}, median: {median}")

# Much faster than sorting after each insertion
# 1000 insertions: O(1000 log 1000) vs O(1000 * 1000 log 1000)

from sortedcontainers import SortedDict
from datetime import datetime, timedelta

class TimeSeries:
    """
    Store time-series data with efficient range queries.
    """

    def __init__(self):
        self.data = SortedDict()

    def add(self, timestamp, value):
        """Add data point. O(log n)"""
        self.data[timestamp] = value

    def get_range(self, start_time, end_time):
        """Get all data in time range. O(log n + k)"""
        result = []
        for timestamp in self.data.irange(start_time, end_time):
            result.append((timestamp, self.data[timestamp]))
        return result

    def get_latest(self, n=1):
        """Get n most recent data points. O(n)"""
        keys = list(self.data.keys())[-n:]
        return [(k, self.data[k]) for k in keys]


# Usage
ts = TimeSeries()

# Add data points
base_time = datetime.now()
for i in range(1000):
    timestamp = base_time + timedelta(seconds=i)
    ts.add(timestamp, i ** 2)

# Query range (very efficient)
start = base_time + timedelta(seconds=100)
end = base_time + timedelta(seconds=200)
range_data = ts.get_range(start, end)
print(f"Found {len(range_data)} points in range")

# Get latest 10 points
latest = ts.get_latest(10)

from sortedcontainers import SortedList
from datetime import datetime, timedelta

class Event:
    def __init__(self, time, description):
        self.time = time
        self.description = description

    def __lt__(self, other):
        return self.time < other.time

    def __repr__(self):
        return f"Event({self.time}, {self.description})"


class EventScheduler:
    """
    Maintain sorted list of events with efficient insertion.
    """

    def __init__(self):
        self.events = SortedList()

    def schedule(self, time, description):
        """Schedule new event. O(log n)"""
        self.events.add(Event(time, description))

    def get_next_events(self, n=5):
        """Get next n events. O(n)"""
        return list(self.events[:n])

    def process_due_events(self, current_time):
        """Process all events up to current time. O(k log n)"""
        due = []
        while self.events and self.events[0].time <= current_time:
            due.append(self.events.pop(0))
        return due


# Usage
scheduler = EventScheduler()
base = datetime.now()

# Schedule events (not in order)
scheduler.schedule(base + timedelta(hours=2), "Meeting")
scheduler.schedule(base + timedelta(hours=1), "Email")
scheduler.schedule(base + timedelta(hours=3), "Call")
scheduler.schedule(base + timedelta(minutes=30), "Reminder")

# Get upcoming events (already sorted)
upcoming = scheduler.get_next_events(3)
for event in upcoming:
    print(event)