Question

What is the first step in the algorithm of stooge sort(after base case)?

(a) apply stooge sort on first 2/3 elements of array

(b) apply stooge sort on last 2/3 elements of array

(c) apply stooge sort on first 1/3 elements of array

(d) compare first and last element of the array

This question was addressed to me in a job interview.

I need to ask this question from Sorting topic in section Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (d) compare first and last element of the array

Easy explanation - The first step in the algorithm of stooge sort is to compare the first and last element of the array and switch them if found out of order. In the second step stooge sort is applied on the first 2/3 elements of the array.