Selection Sort

Selection sort operates by iteratively identifying the smallest unsorted element and placing it into its correct sorted position. The algorithm maintains two subarrays: one fully sorted and the other remaining. Regardless of the initial data distribution, the time complexity remains O(n²), making it suitable primarily for small datasets. Its primary advantage is minimal memory overhead, as sorting occurs in-place.

Algorithm Workflow:

• Scan the unsorted portion to locate the minimum value.
• Swap the found minimum with the first element of the unsorted section.
• Advance the boundary beetween sorted and unsorted segments, repeating until the entire collection is ordered.

func applySelectionSort(input []int) []int {
    if len(input) == 0 {
        return input
    }
    for idx := 0; idx < len(input); idx++ {
        targetPos := idx
        for scan := idx + 1; scan < len(input); scan++ {
            if input[scan] < input[targetPos] {
                targetPos = scan
            }
        }
        if targetPos != idx {
            input[idx], input[targetPos] = input[targetPos], input[idx]
        }
    }
    return input
}

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process repeats until no swaps are required, indicating that the list is sorted. Smaller values gradually move toward the beginning, resembling bubbles rising to the surface. An optimization involves tracking whether any exchanges occurred during a full pass; if a complete traversal finishes without swaps, the algorithm can terminate early.

Algorithm Workflow:

• Compare each pair of adjacent elements from the start to the end of the array.
• Swap elements if the left value exceeds the right value.
• After each pass, the largest unsorted element settles at its final position.
• Repeat passes for progressively shorter unsorted segments until stability is achieved.

func executeBubbleSort(dataset []int) []int {
    n := len(dataset)
    if n <= 1 {
        return dataset
    }
    for pass := 0; pass < n-1; pass++ {
        isSorted := true
        for i := 0; i < n-1-pass; i++ {
            if dataset[i] > dataset[i+1] {
                dataset[i], dataset[i+1] = dataset[i+1], dataset[i]
                isSorted = false
            }
        }
        if isSorted {
            break
        }
    }
    return dataset
}

Binary Tree Right View Extraction

Extracting the rightmost node at each depth level (right view) can be efficiently achieved using a depth-first traversal that prioritizes the right subtree. By recording the first node encountered at each new depth level, we capture the right-side silhouette without requiring explicit level-by-level queue management.

type BinaryNode struct {
    Val   int
    Left  *BinaryNode
    Right *BinaryNode
}

func captureRightView(root *BinaryNode) []int {
    var view []int
    var dfs func(node *BinaryNode, depth int)
    
    dfs = func(node *BinaryNode, depth int) {
        if node == nil {
            return
        }
        if depth == len(view) {
            view = append(view, node.Val)
        }
        dfs(node.Right, depth+1)
        dfs(node.Left, depth+1)
    }
    
    dfs(root, 0)
    return view
}

Quick Sort

Quick sort employs a divide-and-conquer strategy. It selects a pivot element, partitions the array so that values less than or equal to the pivot reside on one side and greater values on the other, and then recursively applies the same logic to the subarrays. The partition step places the pivot in its final sorted position.

Core Mechanics:

• Pivot Selection: Typically chooses an element (often the last or middle) to act as the reference point.
• Partitioning: Rearranges elements around the pivot, ensuring left-side elements are smaller and right-side elements are larger.
• Recursive Sorting: Applies the same partitioning logic to the resulting left and right segments until base cases (single elements or empty ranges) are reached.

func performQuickSort(data []int, lower int, upper int) {
    if lower < upper {
        split := splitArray(data, lower, upper)
        performQuickSort(data, lower, split-1)
        performQuickSort(data, split+1, upper)
    }
}

func splitArray(slice []int, start int, end int) int {
    pivotVal := slice[end]
    i := start - 1
    for j := start; j < end; j++ {
        if slice[j] <= pivotVal {
            i++
            slice[i], slice[j] = slice[j], slice[i]
        }
    }
    slice[i+1], slice[end] = slice[end], slice[i+1]
    return i + 1
}

Heap Sort

Heap sort leverages the properties of a binary heap, specifically a max-heap, to sort elements. It first transforms the array into a valid heap structure, then repeatedly extracts the maximum element (root), places it at the end of the array, and restores the heap property for the remaining elements.

Core Mechanics:

• Heap Construction: Builds a max-heap by sifting down non-leaf nodes from the middle of the array toward the root.
• Extraction & Adjustment: Swaps the root with the last unsorted element, reduces the effective heap size, and sifts down the new root to maintain the max-heap invariant.
• Iteration: Continues until the entire array is sorted in ascending order.

func siftDown(heap []int, size int, parent int) {
    for {
        leftChild := 2*parent + 1
        rightChild := 2*parent + 2
        largest := parent

        if leftChild < size && heap[leftChild] > heap[largest] {
            largest = leftChild
        }
        if rightChild < size && heap[rightChild] > heap[largest] {
            largest = rightChild
        }
        if largest == parent {
            break
        }

        heap[parent], heap[largest] = heap[largest], heap[parent]
        parent = largest
    }
}

func runHeapSort(input []int) {
    n := len(input)
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(input, n, i)
    }
    for i := n - 1; i > 0; i-- {
        input[0], input[i] = input[i], input[0]
        siftDown(input, i, 0)
    }
}

Merge Sort

Merge sort follows a strict divide-and-conquer approach. It recursively splits the dataset into halves until single-element segments are formed, then merges adjacent sorted segments back together while preserving order. The algorithm guarantees O(n log n) time complexity and O(n) auxiliary space, offering stable sorting behavior.

func invokeMergeSort(collection []int) []int {
    if len(collection) <= 1 {
        return collection
    }
    mid := len(collection) / 2
    leftHalf := invokeMergeSort(collection[:mid])
    rightHalf := invokeMergeSort(collection[mid:])
    return combineHalves(leftHalf, rightHalf)
}

func combineHalves(first []int, second []int) []int {
    merged := make([]int, 0, len(first)+len(second))
    i, j := 0, 0
    for i < len(first) && j < len(second) {
        if first[i] < second[j] {
            merged = append(merged, first[i])
            i++
        } else {
            merged = append(merged, second[j])
            j++
        }
    }
    merged = append(merged, first[i:]...)
    merged = append(merged, second[j:]...)
    return merged
}

Storage Indexing and Billion-Row Data Management

B-Trees and B+Trees are balanced multi-way search trees optimized for external storage systems. While both support logarithmic search times, their internal structures dictate different use cases.

B-Tree Characteristics:

• Internal nodes store both keys and associated data payloads.
• Keys partition nodes into ranges, each pointing to a child subtree.
• Data resides across all levels, including root and intermediate nodes.

B+Tree Characteristics:

• Internal nodes act purely as routing indices, storing only keys.
• All actual data records are stored exclusively in leaf nodes.
• Leaf nodes are linked sequentially, enabling efficient range scans without backtracking to parent nodes.
• Higher fan-out due to smaller internal node payloads reduces tree height and minimizes disk I/O.

When engineering systems to handle billion-row datasets, in-memory structures become impractical. The following strategies form the foundation of large-scale data architectures:

• Disk-Oriented Indexing: B+Trees align with block-based storage by packing multiple keys per node, reducing seek times and leveraging sequential read-ahead mechanisms.
• Partitioning & Caching: Dividing tables into physical segments allows operating systems and database buffers to cache only hot data pages, minimizing redundant disk access.
• Horizontal Sharding: Distributing data across multiple nodes reduces per-node load and enables linear scalability through distributed query routing.
• Columnar Storage: Storing data by attribute rather than row drastically cuts I/O for analytical workloads, especially when paired with compression algorithms like Snappy or Zstandard.
• Index Tuning: Deploying composite, covering, or filtered indexes based on query patterns reduces full table scans and accelerates selective lookups.
• Processing Paradigms: Batch frameworks (e.g., Spark, MapReduce) handle historical aggregation, while stream engines (e.g., Flink, Kafka Streams) process continuous event flows with low latency.