Tim Sort Program with Explanation and Code

2025-11-19 tim sort hybrid sorting algorithm insertion sort + merge sort python tim sort c tim sort javascript tim sort php tim sort csharp tim sort optimized sorting algorithm real world sorting

Tim Sort is a hybrid sorting algorithm combining Merge Sort and Insertion Sort, optimized for real-world datasets. It is used as the default sorting algorithm in Python and Java. This page provides explanations and full code examples in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Tim Sort?

Tim Sort is a highly optimized hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It is designed to perform exceptionally well on real-world data by identifying already-sorted sequences (called runs). Python’s built-in sort() and Java’s Arrays.sort() use Tim Sort due to its speed, stability, and adaptability. It efficiently combines insertion sorting for small sections with merging for larger sections.

Steps to Solve

Choose a minimum run size (typically between 32 and 64).
Break the array into small chunks (runs) of size MIN_RUN.
Sort each run using Insertion Sort.
Merge runs in a manner similar to Merge Sort.
Continue merging until the entire array is sorted.
Return the fully sorted output.

Key Points

Time complexity: O(n log n) in worst case.
Stable sorting algorithm.
Uses insertion sort for small runs.
Uses merge sort for efficiently merging sorted runs.
Optimized for real-world partially sorted data.
Used as the default sorting algorithm in major programming languages.

Program Code


MIN_RUN = 32

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 = 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 tim_sort(arr):
    n = len(arr)

    for i in range(0, n, MIN_RUN):
        insertion_sort(arr, i, min(i + MIN_RUN - 1, n - 1))

    size = MIN_RUN
    while size < n:
        for left in range(0, n, 2 * size):
            mid = left + size - 1
            right = min(left + 2 * size - 1, n - 1)

            if mid < right:
                merge(arr, left, mid, right)
        size *= 2

arr = list(map(int, input("Enter numbers: ").split()))
tim_sort(arr)
print("Sorted array:", arr)


#include <stdio.h>
#define MIN_RUN 32

void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void merge(int arr[], int l, int m, int r) {
    int leftSize = m - l + 1;
    int rightSize = r - m;

    int left[leftSize], right[rightSize];

    for (int i = 0; i < leftSize; i++)
        left[i] = arr[l + i];

    for (int i = 0; i < rightSize; i++)
        right[i] = arr[m + 1 + i];

    int i = 0, j = 0, k = l;

    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }

    while (i < leftSize)
        arr[k++] = left[i++];

    while (j < rightSize)
        arr[k++] = right[j++];
}

void timSort(int arr[], int n) {
    for (int i = 0; i < n; i += MIN_RUN) {
        insertionSort(arr, i, (i + MIN_RUN - 1 < n ? i + MIN_RUN - 1 : n - 1));
    }

    for (int size = MIN_RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1 < n ? left + 2 * size - 1 : n - 1);

            if (mid < right)
                merge(arr, left, mid, right);
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    timSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}


const MIN_RUN = 32;

function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    let key = arr[i];
    let j = i - 1;

    while (j >= left && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

function merge(arr, l, m, r) {
  let left = arr.slice(l, m + 1);
  let right = arr.slice(m + 1, r + 1);

  let i = 0, j = 0, k = l;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) arr[k++] = left[i++];
    else arr[k++] = right[j++];
  }

  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[k++] = right[j++];
}

function timSort(arr) {
  let n = arr.length;

  for (let i = 0; i < n; i += MIN_RUN) {
    insertionSort(arr, i, Math.min(i + MIN_RUN - 1, n - 1));
  }

  for (let size = MIN_RUN; size < n; size *= 2) {
    for (let left = 0; left < n; left += 2 * size) {
      let mid = left + size - 1;
      let right = Math.min(left + 2 * size - 1, n - 1);

      if (mid < right) merge(arr, left, mid, right);
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
timSort(arr);
console.log("Sorted array:", arr);


using System;

class Program {

    const int MIN_RUN = 32;

    static void InsertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void Merge(int[] arr, int l, int m, int r) {
        int leftSize = m - l + 1;
        int rightSize = r - m;

        int[] left = new int[leftSize];
        int[] right = new int[rightSize];

        Array.Copy(arr, l, left, 0, leftSize);
        Array.Copy(arr, m + 1, right, 0, rightSize);

        int i = 0, j = 0, k = l;

        while (i < leftSize && j < rightSize) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }

        while (i < leftSize) arr[k++] = left[i++];
        while (j < rightSize) arr[k++] = right[j++];
    }

    static void TimSort(int[] arr) {
        int n = arr.Length;

        for (int i = 0; i < n; i += MIN_RUN)
            InsertionSort(arr, i, Math.Min(i + MIN_RUN - 1, n - 1));

        for (int size = MIN_RUN; size < n; size *= 2) {
            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);
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        TimSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}


<?php

define("MIN_RUN", 32);

function insertionSort(&$arr, $left, $right) {
    for ($i = $left + 1; $i <= $right; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= $left && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }

        $arr[$j + 1] = $key;
    }
}

function mergeArray(&$arr, $l, $m, $r) {
    $left = array_slice($arr, $l, $m - $l + 1);
    $right = array_slice($arr, $m + 1, $r - $m);

    $i = $j = 0;
    $k = $l;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j])
            $arr[$k++] = $left[$i++];
        else
            $arr[$k++] = $right[$j++];
    }

    while ($i < count($left)) $arr[$k++] = $left[$i++];
    while ($j < count($right)) $arr[$k++] = $right[$j++];
}

function timSort(&$arr) {
    $n = count($arr);

    for ($i = 0; $i < $n; $i += MIN_RUN) {
        insertionSort($arr, $i, min($i + MIN_RUN - 1, $n - 1));
    }

    for ($size = MIN_RUN; $size < $n; $size *= 2) {
        for ($left = 0; $left < $n; $left += 2 * $size) {
            $mid = $left + $size - 1;
            $right = min($left + 2 * $size - 1, $n - 1);

            if ($mid < $right)
                mergeArray($arr, $left, $mid, $right);
        }
    }
}

$arr = array_map("intval", explode(" ", readline("Enter numbers: ")));
timSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>