Tim Sort
Tim Sort :
Author(s) : Tim Peters Date : 2002Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently.
| 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
MIN_MERGE = 32
def calcMinRun(n):
r = 0
while n >= MIN_MERGE:
r |= n & 1
n >>= 1
return n + r
def insertionSort(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):
len1, len2 = m - l + 1, r - m
left, right = [], []
for i in range(0, len1):
left.append(arr[l + i])
for i in range(0, len2):
right.append(arr[m + 1 + i])
i, j, k = 0, 0, l
while i < len1 and j < len2:
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len1:
arr[k] = left[i]
k += 1
i += 1
while j < len2:
arr[k] = right[j]
k += 1
j += 1
def timSort(arr):
n = len(arr)
minRun = calcMinRun(n)
for start in range(0, n, minRun):
end = min(start + minRun - 1, n - 1)
insertionSort(arr, start, end)
size = minRun
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 * sizeconst MIN_MERGE = 32;
function calcMinRun(n) {
let r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
function insertionSort(arr, left, right) {
for (let i = left + 1; i <= right; i++) {
let temp = arr[i];
let j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
function merge(arr, l, m, r) {
let len1 = m - l + 1, len2 = r - m;
let left = new Array(len1);
let right = new Array(len2);
for (let x = 0; x < len1; x++) left[x] = arr[l + x];
for (let x = 0; x < len2; x++) right[x] = arr[m + 1 + x];
let i = 0, j = 0, k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < len1) {
arr[k] = left[i];
k++;
i++;
}
while (j < len2) {
arr[k] = right[j];
k++;
j++;
}
}
function timSort(arr) {
let n = arr.length;
let minRun = calcMinRun(n);
for (let i = 0; i < n; i += minRun) {
insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
}
for (let size = minRun; size < n; size = 2 * size) {
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);
}
}
}
}public static int MIN_MERGE = 32;
public static int calcMinRun(int n) {
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
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;
}
}
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];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < len1) {
arr[k] = left[i];
k++;
i++;
}
while (j < len2) {
arr[k] = right[j];
k++;
j++;
}
}
public static void timSort(int[] arr) {
int n = arr.length;
int minRun = calcMinRun(n);
for (int i = 0; i < n; i += minRun) {
insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
}
for (int size = minRun; size < n; size = 2 * size) {
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);
}
}
}
}const MIN_MERGE = 32
func calcMinRun(n int) int {
r := 0
for n >= MIN_MERGE {
r |= n & 1
n >>= 1
}
return n + r
}
func insertionSort(arr []int, left, right int) {
for i := left + 1; i <= right; i++ {
temp := arr[i]
j := i - 1
for j >= left && arr[j] > temp {
arr[j+1] = arr[j]
j--
}
arr[j+1] = temp
}
}
func merge(arr []int, l, m, r int) {
len1, len2 := m-l+1, r-m
left := make([]int, len1)
right := make([]int, len2)
for i := 0; i < len1; i++ {
left[i] = arr[l+i]
}
for i := 0; i < len2; i++ {
right[i] = arr[m+1+i]
}
i, j, k := 0, 0, l
for i < len1 && j < len2 {
if left[i] <= right[j] {
arr[k] = left[i]
i++
} else {
arr[k] = right[j]
j++
}
k++
}
for i < len1 {
arr[k] = left[i]
k++
i++
}
for j < len2 {
arr[k] = right[j]
k++
j++
}
}
func timSort(arr []int) {
n := len(arr)
minRun := calcMinRun(n)
for i := 0; i < n; i += minRun {
end := i + minRun - 1
if end > n-1 {
end = n - 1
}
insertionSort(arr, i, end)
}
for size := minRun; size < n; size = 2 * size {
for left := 0; left < n; left += 2 * size {
mid := left + size - 1
right := left + 2*size - 1
if right > n-1 {
right = n - 1
}
if mid < right {
merge(arr, left, mid, right)
}
}
}
}#define MIN_MERGE 32
int calcMinRun(int n) {
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
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;
}
}
void merge(int arr[], int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
int *left = (int *)malloc(len1 * sizeof(int));
int *right = (int *)malloc(len2 * sizeof(int));
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];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < len1) {
arr[k] = left[i];
k++;
i++;
}
while (j < len2) {
arr[k] = right[j];
k++;
j++;
}
free(left);
free(right);
}
void timSort(int arr[], int n) {
int minRun = calcMinRun(n);
for (int i = 0; i < n; i += minRun) {
int end = (i + minRun - 1 < n - 1) ? (i + minRun - 1) : (n - 1);
insertionSort(arr, i, end);
}
for (int size = minRun; size < n; size = 2 * size) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = (left + 2 * size - 1 < n - 1) ? (left + 2 * size - 1) : (n - 1);
if (mid < right) {
merge(arr, left, mid, right);
}
}
}
}
