Shell sort vs Insertion sort

  Kiến thức lập trình

I did not get why shell sort is more efficient.
so here is a comparison of both algos according to what I have understood:

Insertion Sort: O(n^2) because we go through the whole array at first(kinda to divide it into sorted subarrays) and then the innerloop comes to insert the new element (the elemnt not included in the sorted subarray)
Shell Sort: does exactly what the insertion does but with some pre-work.(making it pretty much sorted) then use insertion.
So shell is basically Pro-work+Insertion. Although I know that the pre-work result in less swapping, we need anyways to go through every element when gap =1.
So why is it useful?

LEAVE A COMMENT