# Lesson 3 - Sorting Algorithms and Divide & Conquer

Please visit the Lesson Page for more detailed info

Session Recordings:
English: https://youtu.be/M6NJUfT14aY
Hindi: https://youtu.be/W0R6m1sX1sY

In this lesson, we explore the sorting problem and apply the divide-and-conquer strategy to come up with efficient algorithms for sorting.

### Notebooks used in this lesson:

2 Likes

Hi guys
how can someone test each individual code in a function to enable one understand it better

I am not sure if I got your question right, but I think you mean you want to test each line of a code of a function that you made? You can give a print statement and check what the above value prints and compare it with what it should print and you can do this for all confusing line in your code and later when you have removed all your confusion you can comment/remove the extra print statements.

Hi,
Could someone explain how the second step is calculated please i.e.,
(2×3)+(2×4+0×3)x+(2×2+3×5+4×0)x^2+(7×3+5×4+0×2)x^3+(7×4+5×2)x^4+(7×2)x^5?

Example:

``````def insertion_sort(nums):
nums = list(nums)
for i in range(len(nums)):
cur = nums.pop(i)
j = i-1
while j >=0 and nums[j] > cur:
j -= 1
j -= 1
nums.insert(j+1, cur)
return nums
``````

Good evening everyone, Sir asked to find the time complexity of `insertion_sort`. Since, seeing the `for loop`, I understood that this loop’s complexity would be O(n) but I was not able to understand the complexity of `while loop`. Therefore, I am not able to tell the complexity of the `insertion_sort`. Can anyone help???

1 more question from this, shouldn’t the `or` replaces `and` in terminating condition of `while` loop as we want either of the two conditions to come to false first? Like I mean that we want that either `j` reaches the starting of the array or the element on `nums[j]` should become smaller than the `cur`? Please help.

The time complexity for the `while` loop depends,
In the best-case scenario (when the list is already sorted) `nums[j] > cur` would always be false and we would never enter the `while` loop.

The overall time complexity, in this case, would be because of the `for` loop (n-1) and `.insert()` (n-1) = `O(n)`.

For the worst-case (when the list is in decreasing order), the `while` loop will be true for all values of `i` in `for` loop.
So, when `i=1` `while` will run 1 time, when `i=2 while` will run 2 times … when `i=n-1` `while` will run `n-1` times.

Therefore, in total the `while` loop runs for `1+2+3......+(n-1)` times,
= (n-1)(n-1+1)/2 {sum of n natural numbers}
= (n^2-n)/2

And the overall time complexity in the worst-case would be `O(n^2)`.

Also, I think we need both `j>=0 & nums[j]>cur` as for comparison and swap, we require the `nums[j]>cur` condition and to check if `nums[j]` don’t go out of bounds we need `j>=0`,
Even in python if `j=-1` then `nums[-1]` would be the last element in the list which should be greater than cur, but we will still keep comparing elements backward even when not required.

1 Like

Thanks for your reply, now I can understand why insertion sort’s complexity was `O(n^1)`.

1 Like

in this when will be the end =None ?

def partition(nums, start=0, end=None):
# print(‘partition’, nums, start, end)
if end is None:
end = len(nums) - 1

``````# Initialize right and left pointers
l, r = start, end-1

# Iterate while they're apart
while r > l:
# print('  ', nums, l, r)
# Increment left pointer if number is less or equal to pivot
if nums[l] <= nums[end]:
l += 1

# Decrement right pointer if number is greater than pivot
elif nums[r] > nums[end]:
r -= 1

# Two out-of-place elements found, swap them
else:
nums[l], nums[r] = nums[r], nums[l]
# print('  ', nums, l, r)
# Place the pivot between the two parts
if nums[l] > nums[end]:
nums[l], nums[end] = nums[end], nums[l]
return l
else:
return end
``````

i

Hey @latchireddiekalavya, If you notice carefully, the default value of `end` is set to `None`. So, when the program will be called for the first time, the value of `end` will be `None` if not specified while calling the function. Hope this will help!!

Hi guys I would like to tell u all something that by default the complexity of the Insertion sort is O(n^2) [time] . So I have updated it a by putting the concept of binary search to it and
made it O(nlogn)< complexity >O(n^2).

And the code for it is attached below have a look
Regards

There are also few edge cases for this
I have made the Insertion Sort to the complexity of O(n^2) to O(nlogn)
See below for the final code