Question

Why is Shell sort called as a generalization of Insertion sort?

(a) Shell sort allows an exchange of far items whereas insertion sort moves elements by one position

(b) Improved lower bound analysis

(c) Insertion is more efficient than any other algorithms

(d) Shell sort performs internal sorting

This question was addressed to me in an interview for internship.

My doubt stems from Shell sort topic in chapter Sorting of Data Structures & Algorithms II

Answer 1

Right option is (a) Shell sort allows an exchange of far items whereas insertion sort moves elements by one position

For explanation: Shell sort is an extension of insertion sort because it swaps elements at far distances and at a faster rate.