TimSort

# Educational TimSort-like hybrid, not production TimSort.
 
MIN_MERGE = 32
 
def calc_min_run(n):
    """Returns the minimum length of a run to be merged"""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r
 
def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        j = i
        while j > left and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1
 
def merge(arr, l, m, r):
    left = arr[l:m + 1]
    right = arr[m + 1:r + 1]
    i = j = 0
    write = l
    while i < len(left) and j < len(right):
        # Taking left on equality preserves stability.
        if left[i] <= right[j]:
            arr[write] = left[i]
            i += 1
        else:
            arr[write] = right[j]
            j += 1
        write += 1
    while i < len(left):
        arr[write] = left[i]
        i += 1
        write += 1
    while j < len(right):
        arr[write] = right[j]
        j += 1
        write += 1
 
def tim_sort(arr):
    n = len(arr)
    if n < 2:
        return arr
    min_run = calc_min_run(n)
    
    # Sort individual subarrays of size min_run
    for start in range(0, n, min_run):
        end = min(start + min_run - 1, n - 1)
        insertion_sort(arr, start, end)
        
    # Merge runs
    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 * size
        
    return arr
 
# Usage
arr = [5, 21, 7, 23, 19]
print(tim_sort(arr))
# In production Python, use: arr.sort()

import java.util.Arrays;

// Educational TimSort-like hybrid, not production TimSort.
public class TimSort {
    static int MIN_MERGE = 32;

    public static int minRunLength(int n) {
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    // Insertion sort for small runs
    public static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    // Merge function
    public static void merge(int[] arr, int l, int m, int r) {
        int len1 = m - l + 1, len2 = r - m;
        int[] left = new int[len1];
        int[] right = new int[len2];
        for (int x = 0; x < len1; x++) left[x] = arr[l + x];
        for (int x = 0; x < len2; x++) right[x] = arr[m + 1 + x];

        int i = 0, j = 0, k = l;
        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }
        while (i < len1) arr[k++] = left[i++];
        while (j < len2) arr[k++] = right[j++];
    }

    public static void timSort(int[] arr) {
        int n = arr.length;
        if (n < 2) return;
        int minRun = minRunLength(n);

        // Sort individual subarrays of size minRun
        for (int i = 0; i < n; i += minRun) {
            insertionSort(arr, i, Math.min((i + minRun - 1), (n - 1)));
        }

        // Merge runs
        for (int size = minRun; size < n; ) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min((left + 2 * size - 1), (n - 1));
                if (mid < right)
                    merge(arr, left, mid, right);
            }
            if (size > n / 2) break; // avoid integer overflow on doubling
            size *= 2;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 21, 7, 23, 19 };
        timSort(arr);
        System.out.println(Arrays.toString(arr));
        // In reality, use Arrays.sort(Object[]) or List.sort(...) for Java's TimSort.
    }
}