Binary search and how sorting algorithms work — Data Structures & Algorithms

8. Binary search and how sorting algorithms work

Basic★ Must knowLesson 8 of 10

Binary search — on sorted data, halve the range each step: O(log n).

csharp

int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;         // avoids int overflow of (lo + hi)
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

Sorting algorithms:

Algorithm	Idea	Best / Avg / Worst	Space	Stable
Bubble	Swap adjacent out-of-order pairs repeatedly	n / n² / n²	1	Yes
Selection	Pick the minimum, put it in front	n² / n² / n²	1	No
Insertion	Insert each item into the sorted left part	n / n² / n²	1	Yes — great for small/nearly sorted
Merge	Split in halves, sort each, merge	n log n (all)	n	Yes
Quick	Pick a pivot, partition smaller/larger, recurse	n log n / n log n / n²	log n	No
Heap	Build a heap, extract max repeatedly	n log n (all)	1	No
Counting/Radix	Count occurrences of small integer keys	n + k	n + k	Yes

csharp

void QuickSort(int[] a, int lo, int hi)
{
    if (lo >= hi) return;
    int pivot = a[(lo + hi) / 2], i = lo, j = hi;
    while (i <= j)
    {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) { (a[i], a[j]) = (a[j], a[i]); i++; j--; }
    }
    QuickSort(a, lo, j); QuickSort(a, i, hi);
}

int[] MergeSort(int[] a)
{
    if (a.Length <= 1) return a;
    var left = MergeSort(a[..(a.Length / 2)]);
    var right = MergeSort(a[(a.Length / 2)..]);
    var result = new int[a.Length];
    int l = 0, r = 0, k = 0;
    while (l < left.Length && r < right.Length) result[k++] = left[l] <= right[r] ? left[l++] : right[r++];
    while (l < left.Length) result[k++] = left[l++];
    while (r < right.Length) result[k++] = right[r++];
    return result;
}

In practice: Array.Sort/List.Sort use introsort (quicksort, switching to heapsort if recursion gets too deep and insertion sort for small parts — unstable); LINQ OrderBy is a stable sort. SQL Server sorts in memory or spills to tempdb when the memory grant is too small.