Tim Sort
Tim Sort :
Author(s) : Tim Peters Date : 2002Timsort is a hybrid sorting algorithm that combines the strengths of insertion sort and merge sort. It is often used in Java's Arrays.sort() method due to its efficiency for most real-world data sets. Timsort initially partitions the input array into runs (partially sorted sub-arrays). For small runs, insertion sort is applied for its speed. When merging larger runs, a variant of merge sort is employed, optimized for already partially sorted data. This hybrid approach makes Timsort generally faster than pure insertion sort or merge sort for most data.
| Time Complexity | O(n log n) |
| Best Case | O(n) |
| Worst Case | O(n log n) |
| Space Complexity | O(n) |
| Stable | Yes |
Code Integration:
* the code might contain some bugs or may not work correctly
def timsort(arr, n):
run_size = 32 # Define a small run size
# Identify natural runs (already sorted subarrays)
for i in range(n):
if i == 0 or arr[i] > arr[i - 1]: # Start of a new run
min_run = max(run_size, i + 1) # Minimum run size (including current element)
while i + 1 < n and arr[i + 1] >= arr[i]: # Extend run if elements are increasing
i += 1
max_run = min(n - i, 2 * run_size) # Limit run size (avoid overflow)
# Minimise run size if two previous runs are large enough
if i > 0 and n - i >= min_run * 2:
# In-place merge with the previous larger run
j = i - min_run
while j < i and arr[j] > arr[i]:
arr[i + 1], arr[j] = arr[j], arr[i + 1]
i += 1
j += 1
# Timsort logic (in-place merging)
for i in range(0, n, run_size): # Loop through potential runs
end_run1 = min(i + run_size, n) # End of first potential run
# Check if next element starts a new run (avoid unnecessary merge)
if end_run1 < n and arr[end_run1] >= arr[end_run1 - 1]:
continue
# Merge current run with the next run (if it exists)
end_run2 = min(end_run1 + run_size, n)
while end_run1 < end_run2:
if arr[end_run1] <= arr[end_run2 - 1]:
end_run1 += 1
else:
temp = arr[end_run2 - 1]
j = end_run2 - 2
while j >= end_run1 and arr[j] > temp:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = temp
end_run1 += 1
end_run2 += 1
# Test array
arr = [12, 11, 13, 5, 6, 7]
timSort(arr, len(arr))
print('Sorted array is:', arr)function timsort(arr, n) {
const run_size = 32; // Define a small run size
// Identify natural runs (already sorted subarrays)
for (let i = 0; i < n; i++) {
if (i === 0 || arr[i] > arr[i - 1]) { // Start of a new run
let min_run = Math.max(run_size, i + 1); // Minimum run size
while (i + 1 < n && arr[i + 1] >= arr[i]) { // Extend run if elements are increasing
i++;
}
const max_run = Math.min(n - i, 2 * run_size); // Limit run size (avoid overflow)
// Minimise run size if two previous runs are large enough
if (i > 0 && n - i >= min_run * 2) {
// In-place merge with the previous larger run
let j = i - min_run;
while (j < i && arr[j] > arr[i]) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j++;
}
}
}
}
// Timsort logic (in-place merging)
for (let i = 0; i < n; i += run_size) {
const end_run1 = Math.min(i + run_size, n); // End of first potential run
// Check if next element starts a new run (avoid unnecessary merge)
if (end_run1 < n && arr[end_run1] >= arr[end_run1 - 1]) {
continue;
}
// Merge current run with the next run (if it exists)
const end_run2 = Math.min(end_run1 + run_size, n);
while (end_run1 < end_run2) {
if (arr[end_run1] <= arr[end_run2 - 1]) {
end_run1++;
} else {
const temp = arr[end_run2 - 1];
let j = end_run2 - 2;
while (j >= end_run1 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
end_run1++;
end_run2++;
}
}
}
}public class Timsort {
private static final int RUN_SIZE = 32; // Define a small run size
public static void sort(int[] arr, int n) {
// Identify natural runs (already sorted subarrays)
for (int i = 0; i < n; i++) {
if (i == 0 || arr[i] > arr[i - 1]) { // Start of a new run
int minRun = Math.max(RUN_SIZE, i + 1); // Minimum run size
while (i + 1 < n && arr[i + 1] >= arr[i]) { // Extend run if increasing
i++;
}
int maxRun = Math.min(n - i, 2 * RUN_SIZE); // Limit run size (avoid overflow)
// Minimise run size if two previous runs are large enough
if (i > 0 && n - i >= minRun * 2) {
// In-place merge with the previous larger run
int j = i - minRun;
while (j < i && arr[j] > arr[i]) {
swap(arr, i, j);
i++;
j++;
}
}
}
}
// Timsort logic (in-place merging)
for (int i = 0; i < n; i += RUN_SIZE) {
int endRun1 = Math.min(i + RUN_SIZE, n); // End of first potential run
// Check if next element starts a new run (avoid unnecessary merge)
if (endRun1 < n && arr[endRun1] >= arr[endRun1 - 1]) {
continue;
}
// Merge current run with the next run (if it exists)
int endRun2 = Math.min(endRun1 + RUN_SIZE, n);
while (endRun1 < endRun2) {
if (arr[endRun1] <= arr[endRun2 - 1]) {
endRun1++;
} else {
int temp = arr[endRun2 - 1];
int j = endRun2 - 2;
while (j >= endRun1 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
endRun1++;
endRun2++;
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}package timsort
const runSize = 32 // Define a small run size
func sort(arr []int, n int) {
// Identify natural runs (already sorted subarrays)
for i := 0; i < n; i++ {
if i == 0 || arr[i] > arr[i-1] { // Start of a new run
minRun := max(runSize, i+1) // Minimum run size (including current element)
for i+1 < n && arr[i+1] >= arr[i] { // Extend run if elements are increasing
i++
}
maxRun := min(n-i, 2*runSize) // Limit run size (avoid overflow)
// Minimise run size if two previous runs are large enough
if i > 0 && n-i >= minRun*2 {
// In-place merge with the previous larger run
j := i - minRun
for j < i && arr[j] > arr[i] {
arr[i], arr[j] = arr[j], arr[i]
i++
j++
}
}
}
}
// Timsort logic (in-place merging)
for i := 0; i < n; i += runSize {
endRun1 := min(i+runSize, n) // End of first potential run
// Check if next element starts a new run (avoid unnecessary merge)
if endRun1 < n && arr[endRun1] >= arr[endRun1-1] {
continue
}
// Merge current run with the next run (if it exists)
endRun2 := min(endRun1+runSize, n)
for endRun1 < endRun2 {
if arr[endRun1] <= arr[endRun2-1] {
endRun1++
} else {
temp := arr[endRun2-1]
j := endRun2 - 2
for j >= endRun1 && arr[j] > temp {
arr[j+1] = arr[j]
j--
}
arr[j+1] = temp
endRun1++
endRun2++
}
}
}
}#include <stdio.h>
#define RUN_SIZE 32 // Define a small run size
void swap(int *a, int *b) {
// Swap function for in-place merging
int temp = *a;
*a = *b;
*b = temp;
}
void timsort(int arr[], int n) {
// Identify natural runs (already sorted subarrays)
for (int i = 0; i < n; i++) {
if (i == 0 || arr[i] > arr[i - 1]) { // Start of a new run
int min_run = (i + 1 > RUN_SIZE) ? i + 1 : RUN_SIZE; // Minimum run size
while (i + 1 < n && arr[i + 1] >= arr[i]) { // Extend run if increasing
i++;
}
int max_run = (n - i > 2 * RUN_SIZE) ? 2 * RUN_SIZE : (n - i); // Limit run size
// Minimise run size if two previous runs are large enough
if (i > 0 && n - i >= min_run * 2) {
// In-place merge with the previous larger run
int j = i - min_run;
while (j < i && arr[j] > arr[i]) {
swap(&arr[i], &arr[j]);
i++;
j++;
}
}
}
}
// Timsort logic (in-place merging)
for (int i = 0; i < n; i += RUN_SIZE) {
int end_run1 = (i + RUN_SIZE < n) ? (i + RUN_SIZE) : n; // End of first potential run
// Check if next element starts a new run (avoid unnecessary merge)
if (end_run1 < n && arr[end_run1] >= arr[end_run1 - 1]) {
continue;
}
// Merge current run with the next run (if it exists)
int end_run2 = (end_run1 + RUN_SIZE < n) ? (end_run1 + RUN_SIZE) : n;
while (end_run1 < end_run2) {
if (arr[end_run1] <= arr[end_run2 - 1]) {
end_run1++;
} else {
int temp = arr[end_run2 - 1];
int j = end_run2 - 2;
while (j >= end_run1 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
end_run1++;
end_run2++;
}
}
}
}
