Day 6
Day 6: Advanced Sorting Algorithms - Insertion Sort and Merge Sort
6/60 Days
Advanced Sorting Algorithms - Insertion Sort and Merge Sort #
Welcome to Day 6 of our 60 Days of Coding Algorithm Challenge! Today, we’ll delve into two more advanced sorting algorithms: Insertion Sort and Merge Sort. These sorting techniques offer different trade-offs in terms of efficiency and complexity.
Insertion Sort #
Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms like Merge Sort.
How It Works: #
- It iterates through the array and, for each element, inserts it into its correct position relative to the already sorted elements on its left.
Example: #
1def insertion_sort(arr):
2 for i in range(1, len(arr)):
3 key = arr[i]
4 j = i - 1
5 while j >= 0 and key < arr[j]:
6 arr[j + 1] = arr[j]
7 j -= 1
8 arr[j + 1] = key
9 return arr
Time Complexity: #
- Best Case: O(n) when the array is already sorted.
- Average and Worst Case: O(n^2) when the array is in reverse order.
Merge Sort #
Merge Sort is a more complex, yet efficient, divide-and-conquer …
Continue Reading
Sign up or log in to access the full lesson and all 60 days of algorithm content.