SORTED METHODS

#computerscience #beginners #algorithms #programming

Insertion Sort
How It Actually Behaves
Insertion Sort maintains two parts of the array:

Left side → always sorted
Right side → unsorted

At each step, it takes one element from the unsorted part and inserts it into the correct position in the sorted part.

Internal Mechanics
When inserting an element:

It doesn’t swap repeatedly (like bubble sort)
It shifts elements to the right and places the value in the correct spot
This makes it more efficient than other O(n²) sorts in practice.

Important Properties

Stable Sort
Equal elements keep their original order
Useful when sorting objects with multiple attributes

In-Place
Uses no extra memory
Only a few variables are needed

Adaptive
If the array is already or nearly sorted → runs very fast (O(n))
Best Use Cases
Small input sizes
Nearly sorted data
Used inside advanced algorithms (like hybrid sorts)

Optimization Insight
Insertion Sort becomes efficient when:

Number of inversions is small
Data is partially sorted
**
Step-by-Step Example**
Input
[5, 3, 4, 1]
Process

Start with index 1 (value = 3)
Compare with 5 → shift 5 → insert 3
Result: [3, 5, 4, 1]

Move to index 2 (value = 4)
Compare with 5 → shift 5

Insert 4
Result: [3, 4, 5, 1]
Move to index 3 (value = 1)
Shift 5, 4, 3

Insert 1
Result: [1, 3, 4, 5]
Python Implementation

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

    return arr

Complexity

Best Case: O(n) when the array is already sorted
Average Case: O(n²)
Worst Case: O(n²)
Space Complexity: O(1)

*When to Use
*
Insertion Sort is useful for small datasets and nearly sorted arrays. It is also commonly used in hybrid sorting algorithms.

MERGE SORT
Merge Sort
How Recursion Works Here

Merge Sort keeps dividing until:

Each subarray has only one element
A single element is always sorted
Then it merges them back in sorted order.

Merge Process

The merge step is the most important:

first it do
Compare elements from two sorted arrays
Always pick the smaller one
Continue until one list is exhausted
Append remaining elements

This guarantees sorted output.

Important Properties

Stable Sort
Maintains relative order of equal elements
Not In-Place
Requires extra memory for merging
Predictable Performance
Always O(n log n), regardless of input

*Why Merge Sort is Fast
*
It reduces problem size by half each time:

Number of levels: log n
Work per level: n
Total work: n log n
Real-World Use
Used in external sorting (large files)
Used in systems where stability matters
Basis for algorithms like Timsort (used in Python)
Key Concept: Divide and Conquer (Merge Sort)

Steps:

Divide problem into smaller parts
Solve each part recursively
Combine results

Step-by-Step Example
Input
[5, 3, 4, 1]

Divide Phase
[5, 3, 4, 1]
→ [5, 3] and [4, 1]
→ [5], [3], [4], [1]

Merge Phase
Merge [5] and [3] → [3, 5]
Merge [4] and [1] → [1, 4]

Now merge [3, 5] and [1, 4]:

Compare 3 and 1 → take 1
Compare 3 and 4 → take 3
Compare 5 and 4 → take 4
Take remaining 5

Final result:

[1, 3, 4, 5]
Python Implementation

def mergeSort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result