Timsort

Problem

Implement the Timsort algorithm to sort an array of integers in ascending order. The function timSort should take an array of integers as input and return a new array containing the sorted integers.

Timsort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort, designed to perform well on many kinds of real-world data.

Algorithm

1. Divide the array into small segments (traditionally 32 or 64 elements in size). Sort each segment using Insertion Sort.
2. Merge the sorted segments using the technique from Merge Sort, with optimization for large, ordered arrays.

Examples:

timSort([9,4,7,3,5,8,1,6,2])
// returns [1,2,3,4,5,6,7,8,9]

Time Complexity

• Best and Average Case: O(n log n), which is typical for efficient sorting algorithms.
• Timsort is particularly optimized for partially sorted arrays, where its complexity can approach O(n).