Question

In: Computer Science

What is TimSort and how does it work? TimSort example with step by step explanation. Algorithm...

  • What is TimSort and how does it work?
  • TimSort example with step by step explanation.
  • Algorithm analysis of Timsort with python implementation, including pseudo code and T(n) time complexity analysis

Solutions

Expert Solution

We divide the Array into blocks known as Run. We sort those runs using insertion sort one by one and then merge those runs using the combine function used in merge sort. If the size of the Array is less than run, then Array gets sorted just by using Insertion Sort. The size of the run may vary from 32 to 64 depending upon the size of the array. Note that the merge function performs well when size subarrays are powers of 2. The idea is based on the fact that insertion sort performs well for small arrays.

  • We consider size of run as 32.
  • We one by one sort pieces of size equal to run
  • After sorting individual pieces, we merge them one by one. We double the size of merged subarrays after every iteration.

# Python3 program to perform basic timSort
MIN_MERGE = 32

def calcMinRun(n):
   """Returns the minimum length of a
   run from 23 - 64 so that
   the len(array)/minrun is less than or
   equal to a power of 2.

   e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33,
   ..., 127=>64, 128=>32, ...
   """
   r = 0
   while n >= MIN_MERGE:
       r |= n & 1
       n >>= 1
   return n + r


# This function sorts array from left index to
# to right index which is of size atmost RUN
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


# Merge function merges the sorted runs
def merge(arr, l, m, r):
  
   # original array is broken in two parts
   # left and right array
   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
  
   # after comparing, we merge those two array
   # in larger sub array
   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

   # Copy remaining elements of left, if any
   while i < len1:
       arr[k] = left[i]
       k += 1
       i += 1

   # Copy remaining element of right, if any
   while j < len2:
       arr[k] = right[j]
       k += 1
       j += 1


# Iterative Timsort function to sort the
# array[0...n-1] (similar to merge sort)
def timSort(arr):
   n = len(arr)
   minRun = calcMinRun(n)
  
   # Sort individual subarrays of size RUN
   for start in range(0, n, minRun):
       end = min(start + minRun - 1, n - 1)
       insertionSort(arr, start, end)

   # Start merging from size RUN (or 32). It will merge
   # to form size 64, then 128, 256 and so on ....
   size = minRun
   while size < n:
      
       # Pick starting point of left sub array. We
       # are going to merge arr[left..left+size-1]
       # and arr[left+size, left+2*size-1]
       # After every merge, we increase left by 2*size
       for left in range(0, n, 2 * size):

           # Find ending point of left sub array
           # mid+1 is starting point of right sub array
           mid = min(n - 1, left + size - 1)
           right = min((left + 2 * size - 1), (n - 1))

           # Merge sub array arr[left.....mid] &
           # arr[mid+1....right]
           merge(arr, left, mid, right)

       size = 2 * size


# Driver program to test above function
if __name__ == "__main__":

   arr = [-2, 7, 15, -14, 0, 15, 0,
       7, -7, -4, -13, 5, 8, -14, 12]

   print("Given Array is")
   print(arr)

   # Function Call
   timSort(arr)

   print("After Sorting Array is")
   print(arr)
   # [-14, -14, -13, -7, -4, -2, 0, 0,
       5, 7, 7, 8, 12, 15, 15]

Worst complexity: n*log(n)

Average complexity: n*log(n)

Best complexity: n

Space complexity: n

 

 

Related Solutions

What is the immunological explanation fow how vaccines work?
What is the immunological explanation fow how vaccines work?
Show, step by step, how the stack-based algorithm will transform the expression (1 + 2) *...
Show, step by step, how the stack-based algorithm will transform the expression (1 + 2) * (7 − 2) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.
Explain briefly what the following algorithm does and write the output below: (5 credits) Step 1:...
Explain briefly what the following algorithm does and write the output below: (5 credits) Step 1: Set sum equal to 0, set n equal to 1 Step 2: Repeat steps 3, 4 and 5 until sum > 60 Step 3: Set sum equal to sum + n2 Step 4: Replace n with n +1 Step 5: Print n and sum on a new line Step 6: Stop Show output:
What does the Context Algorithm do? Full explain with example plz.(probability problem)
What does the Context Algorithm do? Full explain with example plz.(probability problem)
what is nutrisystem and how does it work?
what is nutrisystem and how does it work?
What is a buffer and how does it work?
What is a buffer and how does it work?
step by step explanation how to create a youtube channel for business? three paragraphs describing the...
step by step explanation how to create a youtube channel for business? three paragraphs describing the benefits of the social media for small business?
Kernel Compilation full step by step explanation.
Kernel Compilation full step by step explanation.
What is outsourcing and how does it reduce risk? Not how does it work, how does...
What is outsourcing and how does it reduce risk? Not how does it work, how does it work to reduce risk?
Explain what are the requirements for Retaining Wall Design. Need explanation and step by step solution...
Explain what are the requirements for Retaining Wall Design. Need explanation and step by step solution and without plagrism
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT