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.

See them in motion: watch insertion sort and merge sort animate 100 values step by step in our free interactive visualizers.

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 sorting algorithm. It splits the array into halves, sorts each half, and then merges them back together.

How It Works:#

• Divide the array into two halves.
• Conquer by recursively sorting each half.
• Combine the two halves by merging them into a single sorted array.

Example:#

 1def merge_sort(arr):
 2    if len(arr) > 1:
 3        mid = len(arr) // 2
 4        left_half = arr[:mid]
 5        right_half = arr[mid:]
 6
 7        merge_sort(left_half)
 8        merge_sort(right_half)
 9
10        i = j = k = 0
11
12        while i < len(left_half) and j < len(right_half):
13            if left_half[i] < right_half[j]:
14                arr[k] = left_half[i]
15                i += 1
16            else:
17                arr[k] = right_half[j]
18                j += 1
19            k += 1
20
21        while i < len(left_half):
22            arr[k] = left_half[i]
23            i += 1
24            k += 1
25
26        while j < len(right_half):
27            arr[k] = right_half[j]
28            j += 1
29            k += 1
30
31    return arr

Time Complexity:#

• All Cases: O(n log n), making it more efficient than Bubble, Selection, or Insertion Sort for large datasets.

Comparison of Insertion Sort and Merge Sort#

• Insertion Sort is simple and works well for small or nearly sorted arrays but is inefficient for large datasets.
• Merge Sort is more complex but handles large datasets efficiently due to its O(n log n) time complexity.

Exercise#

1. Implement the Merge Sort algorithm and test it on arrays of various sizes.
2. Compare the performance of Insertion Sort and Merge Sort on the same dataset.
3. Modify the Insertion Sort algorithm to handle a list of strings instead of numbers.

Summary#

Understanding these advanced sorting algorithms is essential for writing efficient code. While Insertion Sort is simple and intuitive, Merge Sort introduces the power of the divide-and-conquer approach. Tomorrow, we’ll explore another powerful algorithm: Quick Sort.

Stay tuned!

Solution#

 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
10
11
12# Works unchanged on strings because < compares them lexicographically
13words = ["pear", "apple", "cherry", "banana"]
14print(insertion_sort(words))  # ['apple', 'banana', 'cherry', 'pear']
15
16numbers = [5, 2, 9, 1, 7]
17print(insertion_sort(numbers))  # [1, 2, 5, 7, 9]