Engineering Questions with Answers - Multiple Choice Questions
Timsort MCQ’s
1 - Question
Which of the following is Python’s standard sorting algorithm?
a) quick sort
b) introsort
c) merge sort
d) tim sortAnswer: d
Explanation: Tim sort has been python’s standard sorting algorithm since its version 2.3. It is an example of hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.
View Answer
Answer: d
Explanation: Tim sort has been python’s standard sorting algorithm since its version 2.3. It is an example of hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.
2 - Question
Which of the following sorting algorithm is a constituent of tim sort?
a) selection sort
b) quick sort
c) merge sort
d) heap sort
View Answer
Answer: c
Explanation: Tim sort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It is derived from insertion sort and merge sort.
3 - Question
Tim sort begins sorting the given array by using which of the following sorting algorithm?
a) selection sort
b) quick sort
c) insertion sort
d) merge sort
View Answer
Answer: c
Explanation: Tim sort begins sorting any given array by using insertion sort for each run. The array is divided into smaller parts for this purpose, each part having a size equal to value of run. Then these small parts called runs are merged in order to obtain sorted array.
4 - Question
Which of the following sorting algorithm is stable?
a) Tim sort
b) Introsort
c) Quick sort
d) Heap sort
View Answer
Answer: a
Explanation: Out of the given options Tim sort is the only algorithm which is stable. As both constituents of Tim sort (I.e insertion sort and merge sort) are stable so Tim sort also becomes stable.
5 - Question
Which of the following sorting algorithm is not in-place?
a) insertion sort
b) tim sort
c) quick sort
d) intro sort
View Answer
Answer: b
Explanation: Tim sort is not an in-place sorting algorithm as it requires auxiliary space. It is because it requires to merge sorted runs which requires a third array of the size equal to the sum of the two runs.
6 - Question
Tim sort is a comparison based sort.
a) true
b) false
View Answer
Answer: a
Explanation: Merge sort and insertion sort are comparison based sorts. Thus overall Tim sort also becomes a comparison based sort.
7 - Question
What is the best case time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: a
Explanation: Best case time complexity of Tim sort occurs when the input array is already sorted. In such a case only one run will be required.
8 - Question
What is the worst case time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: Worst case time complexity of Tim sort is O(n log n). It is because the worst complexity of merge sort is O(n log n) and insertion sort is only applied for small arrays.
9 - Question
What is the average time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: Average time complexity of Tim sort remains to be O(n log n). It is the same as the average case complexity of merge sort.
10 - Question
What is the auxiliary space requirement of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: a
Explanation: Tim sort is a hybrid of merge sort and insertion sort. It requires to merge sorted runs which require a third array of the size equal to the sum of the two runs. So in worst case the auxiliary space requirement will be O(n).
11 - Question
Which of the following algorithm is implemented internally in java when we use function arrays.sort()?
a) intro sort
b) quick sort
c) tim sort
d) merge sort
View Answer
Answer: c
Explanation: Java makes use of Tim sort internally for implementing arrays.sort(). It is mainly due to the fastness of this algorithm in comparison to other comparison based sorts.
12 - Question
Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for Tim sort implementation?
a) Because insertion sort is faster and adaptive
b) Because insertion sort requires less space
c) Because insertion sort is easy to implement
d) Because insertion sort is easy to understand
View Answer
Answer: a
Explanation: When small arrays need to be sorted then insertion sort proves to be the best choice. Also, it is adaptive so it performs better than others when the given array is fully/partially sorted.
13 - Question
In which case will tim sort will work as an insertion sort?
a) when no. of elements are less than 64
b) when no. of elements are greater than 64
c) when no. of elements are less than size of run
d) when no. of elements are less than 32
View Answer
Answer: c
Explanation: Tim sort uses a hybrid of insertion and merge sort. It reduces to insertion sort when the size of array is less than the size of run as insertion sort is efficient in sorting small arrays.
14 - Question
What is the usual size of a run in tim sort?
a) 32
b) less than 32
c) 32-64 depending on size of the array
d) 64Answer: c
Explanation: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to maintain balance while merging the sorted runs.
View Answer
Answer: c
Explanation: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to maintain balance while merging the sorted runs.
15 - Question
What will be the output of the given Java code?
import java.util.Arrays; public class SortExample { public static void main(String[] args) { // Our arr contains 8 elements int[] arr = {10,7,9,5,8,4}; Arrays.sort(arr); System.out.printf(Arrays.toString(arr)); } }
a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) 4,5,7,8,9,10
d) error
View Answer
Answer: a
Explanation: The given program sorts the input in ascending order by using the function Arrays.sort(). It uses Tim sort internally
16 - Question
What will be the output of the given Java code?
import java.util.Arrays; public class SortExample { public static void main(String[] args) { int[] arr = {10,7,9,5,8,4}; Arrays.sort(arr, 1, 3); System.out.printf(Arrays.toString(arr)); } }
a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) [10,5,7,8,9,4]
d) [10,7,9,5,8,4]
View Answer
Answer: d
Explanation: The given program sorts only a portion of the input array. It is done by passing two extra arguments to the function Arrays.sort(). It sorts the elements between index 1 and 2.