Tim Sort is a modern and powerful sorting algorithm that is designed to work very well with real-world data. It is not a completely new idea but a smart combination of two simple algorithms that beginners often learn first, which are Insertion Sort and Merge Sort. Tim Sort takes advantage of the fact that real data is often partially sorted already, and it uses this to sort faster than many traditional algorithms.
with hands-on learning.
get the skills and confidence to land your next move.
This algorithm matters a lot because it is used behind the scenes in many popular programming languages. Python and Java use Tim Sort as their default sorting algorithm for arrays and lists. Learning Tim Sort helps beginners understand how simple ideas can be combined to build something efficient and practical. In TypeScript, implementing Tim Sort is a great learning exercise because it strengthens your understanding of loops, functions, and array manipulation.
Program 1: Basic Tim Sort Using Insertion Sort and Merge Sort
This program shows a simple and clear implementation of Tim Sort in TypeScript. It uses Insertion Sort for small sections of the array and Merge Sort to combine those sections.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSort(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
}
for (let size = 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);
}
}
}
return arr;
}
let data: number[] = [5, 21, 7, 23, 19, 10, 12, 3];
console.log("Sorted array:", timSort(data));This program works by first sorting small chunks of the array using Insertion Sort. After that, it merges those sorted chunks using Merge Sort logic. Beginners can understand this as first cleaning small sections and then carefully combining them into a fully sorted array.
Program 2: Tim Sort with Smaller Run Size for Learning
This version reduces the run size to make the algorithm easier to follow and debug.
const SMALL_RUN = 4;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSortSmallRun(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += SMALL_RUN) {
insertionSort(arr, i, Math.min(i + SMALL_RUN - 1, n - 1));
}
for (let size = SMALL_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);
}
}
}
return arr;
}
let values: number[] = [9, 4, 6, 2, 8, 1, 3, 5];
console.log("Sorted array:", timSortSmallRun(values));Using a smaller run size makes it easier for beginners to see how the array is divided and merged. This version is very helpful for learning and experimenting with the algorithm.
Program 3: Tim Sort Using While Loops
This program uses while loops instead of for loops to control the flow.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSortWhile(arr: number[]): number[] {
let n = arr.length;
let i = 0;
while (i < n) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
i += RUN;
}
let size = RUN;
while (size < n) {
let left = 0;
while (left < n) {
let mid = left + size - 1;
let right = Math.min(left + 2 * size - 1, n - 1);
if (mid < right) {
merge(arr, left, mid, right);
}
left += 2 * size;
}
size *= 2;
}
return arr;
}
let nums: number[] = [40, 20, 60, 10, 50, 30];
console.log("Sorted array:", timSortWhile(nums));This version helps beginners understand that the algorithm logic stays the same even when loop styles change. It builds confidence in controlling program flow.
Program 4: Tim Sort with Already Sorted Data
This program applies Tim Sort to an already sorted array.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSort(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
}
for (let size = 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);
}
}
}
return arr;
}
let sortedData: number[] = [1, 2, 3, 4, 5, 6, 7];
console.log("Sorted array:", timSort(sortedData));Tim Sort performs very well here because it detects ordered data quickly. Beginners learn why Tim Sort is preferred in many real-world applications.
Program 5: Tim Sort with Duplicate Values
This program shows how Tim Sort handles repeated numbers.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSort(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
}
for (let size = 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);
}
}
}
return arr;
}
let duplicates: number[] = [4, 2, 2, 8, 3, 3, 1];
console.log("Sorted array:", timSort(duplicates));Tim Sort is stable, which means it keeps the original order of equal elements. This makes it very useful for sorting records and structured data.
Program 6: Tim Sort with Floating Point Numbers
This program demonstrates sorting decimal values.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSort(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
}
for (let size = 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);
}
}
}
return arr;
}
let decimals: number[] = [3.5, 1.2, 4.8, 2.9, 0.6];
console.log("Sorted array:", timSort(decimals));Tim Sort works naturally with floating point numbers. Beginners can use it for prices, measurements, and scientific data without any changes.
Program 7: Tim Sort with Negative Numbers
This program confirms that Tim Sort handles negative values correctly.
const RUN = 32;
function insertionSort(arr: number[], left: number, right: number): void {
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: number[], left: number, mid: number, right: number): void {
let len1 = mid - left + 1;
let len2 = right - mid;
let leftArr = arr.slice(left, mid + 1);
let rightArr = arr.slice(mid + 1, right + 1);
let i = 0, j = 0, k = left;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < len1) {
arr[k++] = leftArr[i++];
}
while (j < len2) {
arr[k++] = rightArr[j++];
}
}
function timSort(arr: number[]): number[] {
let n = arr.length;
for (let i = 0; i < n; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
}
for (let size = 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);
}
}
}
return arr;
}
let mixedNumbers: number[] = [-10, 7, -3, 2, 0, -5, 9];
console.log("Sorted array:", timSort(mixedNumbers));This example builds trust in the algorithm. No special tweaks are needed, which makes Tim Sort beginner-friendly and reliable.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Tim Sort in TypeScript.
Q1. What makes Tim Sort different from other sorting algorithms?
Tim Sort combines Insertion Sort and Merge Sort and takes advantage of already sorted data.
Q2. Is Tim Sort stable?
Yes, Tim Sort is stable and keeps the relative order of equal elements.
Q3. Why is Tim Sort used in real programming languages?
It performs very well on real-world data and handles many edge cases efficiently.
Q4. Can beginners implement Tim Sort in TypeScript?
Yes, breaking it into small functions makes it easy to understand and practice.
Q5. Does Tim Sort work with negative and decimal numbers?
Yes, Tim Sort handles both without any extra logic.
Conclusion
Tim Sort is a smart and practical sorting algorithm that blends simplicity with performance. In this article, we explored several TypeScript programs that implement Tim Sort using different approaches, loop styles, and data types. Each example showed how the algorithm works and why it is trusted in real software systems.
If you are learning TypeScript and want to improve your understanding of sorting algorithms, practicing Tim Sort is an excellent step. Try changing the input data, adjusting the run size, and running the code yourself. With time and practice, you will gain confidence and be ready to explore even more advanced algorithms.
