Basic Sorting Techniques

In the previous lesson, we learned how recursion works and why it is useful for breaking problems into smaller subproblems.

Now we move to one of the most fundamental topics in algorithms: sorting.

Sorting is the process of arranging data in a specific order, usually ascending or descending.

Almost every real-world application relies on sorting in some form.

Why Sorting Is So Important

Sorting is not just about neatness.

Many algorithms become faster and simpler once the data is sorted.

Examples:

Searching in a sorted list is faster than in an unsorted list. Databases sort records to optimize queries. E-commerce sites sort products by price or rating.

Because of this, sorting algorithms are studied very early in algorithm design.

What Makes a Good Sorting Algorithm?

When comparing sorting algorithms, we usually look at:

• Time complexity
• Space usage
• Stability (order of equal elements)
• Simplicity of implementation

No single sorting algorithm is best for all situations.

Overview of Basic Sorting Techniques

Before learning advanced sorting methods like Merge Sort and Quick Sort, we start with basic techniques.

These algorithms are easy to understand and help build strong foundations.

The most common basic sorting algorithms are:

• Bubble Sort
• Selection Sort
• Insertion Sort

Bubble Sort – Idea

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

With each pass, the largest element “bubbles up” to the end of the list.

Bubble Sort Example

Consider this list:

[5, 1, 4, 2]

After the first pass, the largest value moves to the end.

This continues until the list is sorted.

arr = [5, 1, 4, 2]

for i in range(len(arr)):
    for j in range(0, len(arr) - i - 1):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]

print(arr)

Bubble Sort is easy to understand but inefficient for large inputs.

Time complexity: O(n²)

Selection Sort – Idea

Selection Sort works by selecting the smallest element from the unsorted part and placing it at the beginning.

The list is divided into two parts: sorted and unsorted.

Selection Sort Example

arr = [64, 25, 12, 22, 11]

for i in range(len(arr)):
    min_index = i
    for j in range(i + 1, len(arr)):
        if arr[j] < arr[min_index]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]

print(arr)

Selection Sort always performs the same number of comparisons.

Time complexity: O(n²)

Insertion Sort – Idea

Insertion Sort builds the sorted list one element at a time.

It works the same way we sort playing cards in our hand.

Insertion Sort Example

arr = [12, 11, 13, 5, 6]

for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

print(arr)

Insertion Sort performs very well on small or nearly sorted data.

Best case: O(n)

Worst case: O(n²)

Real-World Insight

Modern programming languages use advanced versions of insertion sort for small datasets.

Understanding these basics helps you appreciate why advanced algorithms exist.

Mini Practice

Think carefully:

• Why is Bubble Sort rarely used in production?
• Which algorithm works best for nearly sorted data?

Exercises

Quick Quiz

In the next lesson, we will study Merge Sort and see how recursion and sorting combine to create a much faster algorithm.