Tim Sort

Tim Sort

Tim sort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subset, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is used to sort arrays of non-primitive type in Java SE 7,^[2] on the Android platform,^[3] and in GNU Octave.^[4]

Tim sort
Class	Sorting algorithm
Data structure	Array
Worst case performance	[1]
Best case performance
Average case performance
Worst case space complexity

Example

Algorithm

  While (true):

      let A = pop(stack);

      let B = pop(stack);

      let C = pop(stack);

      If A + B > C:

         push(stack, merge(B, C));

         push(A);

      Else If A > B:

         push(stack, C);

         push(stack, merge(A, B);

      Else:

       break;