Go for Sort: Part 1 - Exploring the Fundamentals and Implementing Insertion Sort

Hello! Welcome to this post where we'll explore the fascinating world of sorting algorithms. As a follow-up to my previous post on search algorithms, particularly binary search, it's crucial to understand that binary search requires sorted input. In this article, we'll define what it means for data to be sorted and explore various methods to achieve this ordering. As usual, all the code examples are provided in the Go programming language. However, I am confident that even if you're not familiar with Go but have programming experience, you'll be able to understand the examples with minimal effort. Alright, here we go. What does it mean for something to be "sorted"? Well, first thing that comes to my mind is that something has some kind of an order, or there is the sequence of the things that follows predefined rules. Consider a box of apples of various colors. If we decide to group them into separate boxes based on their color, what is that process called? That's right – sorting! With numbers, the concept of order is intuitive: 1 is less than 2, 2 is less than 3, and this pattern continues. How can we leverage this natural ordering? Well, we can create a sequence where numbers follow this rule: starting with the smallest, ending with the largest, and ensuring that each element is greater than or equal to the preceding one and less than or equal to the following one. Because sorting enables the efficient arrangement of massive datasets, making information retrieval a breeze, it stands as a cornerstone of computer science, underpinning countless applications from database management to search engines. In this series of posts, we are going to look at a few different algorithms, and to start, let's dive into something called Insertion Sort. This sorting algorithm is quite intuitive because it reminds us of how we might sort a hand of playing cards. Imagine you're holding a hand of cards dealt one by one. As you receive each new card, you look at the cards you're already holding and insert the new card into its correct position within your hand, ensuring that the cards in your hand are always sorted. You might shift some of the existing cards to the right to make space for the new one. Insertion Sort works in a similar way with arrays or lists. It iterates through the elements, and for each element, it compares it with the elements before it. If the current element is smaller than the preceding elements, it "inserts" it into the correct sorted position by shifting the larger elements to the right. Let's illustrate this with an example. Suppose we have the following unsorted array of numbers: [5, 2, 4, 6, 1, 3]. Here's how Insertion Sort would process it step by step: Start with the second element (2). Compare it with the element before it (5). Since 2 is smaller than 5, we move 5 to the right and insert 2 in its place: [2, 5, 4, 6, 1, 3]. The first two elements are now sorted. Move to the third element (4). Compare it with the elements before it (5 and 2). 4 is smaller than 5, so we shift 5 to the right. Now compare 4 with 2. Since 4 is greater than 2, we insert 4 in its current position: [2, 4, 5, 6, 1, 3]. The first three elements are now sorted. Consider the fourth element (6). Compare it with the elements before it (5, 4, and 2). 6 is greater than all of them, so it remains in its current position: [2, 4, 5, 6, 1, 3]. The first four elements are sorted. Move to the fifth element (1). Compare it with 6, 5, 4, and 2. 1 is smaller than all of them. We shift 6, 5, 4, and 2 to the right and insert 1 at the beginning: [1, 2, 4, 5, 6, 3]. The first five elements are sorted. Finally, consider the last element (3). Compare it with 6, 5, 4, 2, and 1. 3 is smaller than 6, 5, and 4, so we shift them to the right. 3 is greater than 2, so we insert 3 in its correct position: [1, 2, 3, 4, 5, 6]. Now the entire array is sorted! This step-by-step process of taking an element and inserting it into its correct sorted position within the already sorted portion of the array is the essence of Insertion Sort. Now to the coding example: package main import "fmt" // InsertionSort sorts an integer slice func InsertionSort(arr []int) { for i := 1; i 0 && arr[j-1] > arr[j] { arr[j], arr[j-1] = arr[j-1], arr[j] j = j - 1 } } } func main() { unsortedArray := []int{5, 2, 4, 6, 1, 3} fmt.Println("Unsorted array:", unsortedArray) InsertionSort(unsortedArray) fmt.Println("Sorted array:", unsortedArray) } When you run this Go code, you will see the following output: Unsorted array: [5 2 4 6 1 3] Sorted array: [1 2 3 4 5 6] This clearly shows how the InsertionSort function takes an unsorted array and modifies it in-place to produce a sorted array. Time Complexity of Insertion Sort: To understand how efficient Insertion Sort is, we need to consider its time complexity in different scenarios: Worst-case: The worst-case scenario occurs when the input arr

Apr 28, 2025 - 08:38

Go for Sort: Part 1 - Exploring the Fundamentals and Implementing Insertion Sort

Hello! Welcome to this post where we'll explore the fascinating world of sorting algorithms. As a follow-up to my previous post on search algorithms, particularly binary search, it's crucial to understand that binary search requires sorted input. In this article, we'll define what it means for data to be sorted and explore various methods to achieve this ordering.

As usual, all the code examples are provided in the Go programming language. However, I am confident that even if you're not familiar with Go but have programming experience, you'll be able to understand the examples with minimal effort.

Alright, here we go. What does it mean for something to be "sorted"? Well, first thing that comes to my mind is that something has some kind of an order, or there is the sequence of the things that follows predefined rules. Consider a box of apples of various colors. If we decide to group them into separate boxes based on their color, what is that process called? That's right – sorting! With numbers, the concept of order is intuitive: 1 is less than 2, 2 is less than 3, and this pattern continues. How can we leverage this natural ordering? Well, we can create a sequence where numbers follow this rule: starting with the smallest, ending with the largest, and ensuring that each element is greater than or equal to the preceding one and less than or equal to the following one. Because sorting enables the efficient arrangement of massive datasets, making information retrieval a breeze, it stands as a cornerstone of computer science, underpinning countless applications from database management to search engines.

In this series of posts, we are going to look at a few different algorithms, and to start, let's dive into something called Insertion Sort. This sorting algorithm is quite intuitive because it reminds us of how we might sort a hand of playing cards.

Imagine you're holding a hand of cards dealt one by one. As you receive each new card, you look at the cards you're already holding and insert the new card into its correct position within your hand, ensuring that the cards in your hand are always sorted. You might shift some of the existing cards to the right to make space for the new one.

Insertion Sort works in a similar way with arrays or lists. It iterates through the elements, and for each element, it compares it with the elements before it. If the current element is smaller than the preceding elements, it "inserts" it into the correct sorted position by shifting the larger elements to the right.

Let's illustrate this with an example. Suppose we have the following unsorted array of numbers: [5, 2, 4, 6, 1, 3].

Here's how Insertion Sort would process it step by step:

Start with the second element (2). Compare it with the element before it (5). Since 2 is smaller than 5, we move 5 to the right and insert 2 in its place: [2, 5, 4, 6, 1, 3]. The first two elements are now sorted.
Move to the third element (4). Compare it with the elements before it (5 and 2). 4 is smaller than 5, so we shift 5 to the right. Now compare 4 with 2. Since 4 is greater than 2, we insert 4 in its current position: [2, 4, 5, 6, 1, 3]. The first three elements are now sorted.
Consider the fourth element (6). Compare it with the elements before it (5, 4, and 2). 6 is greater than all of them, so it remains in its current position: [2, 4, 5, 6, 1, 3]. The first four elements are sorted.
Move to the fifth element (1). Compare it with 6, 5, 4, and 2. 1 is smaller than all of them. We shift 6, 5, 4, and 2 to the right and insert 1 at the beginning: [1, 2, 4, 5, 6, 3]. The first five elements are sorted.
Finally, consider the last element (3). Compare it with 6, 5, 4, 2, and 1. 3 is smaller than 6, 5, and 4, so we shift them to the right. 3 is greater than 2, so we insert 3 in its correct position: [1, 2, 3, 4, 5, 6].

Now the entire array is sorted!

This step-by-step process of taking an element and inserting it into its correct sorted position within the already sorted portion of the array is the essence of Insertion Sort. Now to the coding example:

package main

import "fmt"

// InsertionSort sorts an integer slice
func InsertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        j := i
        for j > 0 && arr[j-1] > arr[j] {
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j = j - 1 
        }
    }
}

func main() {
    unsortedArray := []int{5, 2, 4, 6, 1, 3}
    fmt.Println("Unsorted array:", unsortedArray)

    InsertionSort(unsortedArray)

    fmt.Println("Sorted array:", unsortedArray)
}

When you run this Go code, you will see the following output:
Unsorted array: [5 2 4 6 1 3]
Sorted array: [1 2 3 4 5 6]

This clearly shows how the InsertionSort function takes an unsorted array and modifies it in-place to produce a sorted array.

Time Complexity of Insertion Sort:

To understand how efficient Insertion Sort is, we need to consider its time complexity in different scenarios:

Worst-case: The worst-case scenario occurs when the input array is sorted in reverse order. In this case, for each element, we have to compare it with all the preceding elements and shift them to the right. This results in approximately n(n-1)/2 comparisons and swaps, where n is the number of elements in the array. Therefore, the worst-case time complexity of Insertion Sort is O(n²).
Best-case: The best-case scenario happens when the input array is already sorted. In this situation, for each element, we only need to perform one comparison with the element before it, and no swaps are needed. Thus, the best-case time complexity of Insertion Sort is O(n).
Average-case: In the average case, where the elements in the input array are in a random order, we can expect to perform approximately half the number of comparisons and shifts as in the worst case. Therefore, the average-case time complexity of Insertion Sort is also O(n²).

Insertion Sort is efficient for small datasets or for datasets that are nearly sorted. Its simplicity and low overhead make it a good choice in such cases. However, for larger, unsorted datasets, algorithms with better average and worst-case time complexities, like Merge Sort or Quick Sort, are generally preferred.

That wraps up our exploration of Insertion Sort. In the next post, we'll delve into the characteristics and implementation of another fundamental sorting algorithm. Stay tuned!