Sorting and Searching Algorithms in architect-awesome: A Complete Reference Guide

The architect-awesome repository provides concise explanations of essential sorting and searching algorithms with time/space complexity analysis and Java implementation examples.

The xingshaocheng/architect-awesome repository serves as a comprehensive cheat-sheet for software architects, documenting core algorithms with practical complexity metrics. This guide extracts and explains every sorting and searching algorithm detailed in the repository's README.md, providing runnable Java implementations and architectural insights for production systems.

Sorting Algorithms Explained

The repository documents twelve distinct sorting algorithms in the README.md section 常用算法 → 排序、查找算法. Each entry includes the Chinese algorithm name, core concept, and Big-O characteristics.

Elementary Comparison Sorts (O(n²))

These algorithms suit small datasets or nearly sorted inputs where implementation simplicity outweighs raw performance.

Selection Sort (选择排序) repeatedly scans the unsorted portion to find the minimum element, swapping it to the front of the sorted boundary. It performs exactly O(n²) comparisons but only O(n) swaps, making it efficient when write operations are expensive. Space complexity remains O(1).

Bubble Sort (冒泡排序) compares adjacent elements and swaps them if out of order, causing larger values to "bubble" toward the end. While the worst-case remains O(n²), the repository notes an optimization: if no swaps occur during a pass, the algorithm terminates early, yielding O(n) best-case performance. Space usage is O(1).

Insertion Sort (插入排序) builds the final sorted array one element at a time by inserting each new element into its proper position within the already-sorted portion. Like Bubble Sort, it achieves O(n) best-case when the input is nearly sorted, but degrades to O(n²) for reverse-ordered data. It requires only O(1) auxiliary space.

Efficient Comparison Sorts (O(n log n))

These divide-and-conquer strategies dominate general-purpose sorting in production systems.

Quick Sort (快速排序) selects a pivot element, partitions the array into elements less than and greater than the pivot, then recursively sorts the sub-arrays. The repository emphasizes its O(n log n) average-case efficiency, though poor pivot selection degrades to O(n²). It is in-place but requires O(log n) stack space for recursion. The README.md notes this as the preferred algorithm for primitive arrays in Java.

Merge Sort (归并排序) recursively splits the array in half until reaching single elements, then merges sorted halves back together. It guarantees O(n log n) time regardless of input distribution and is stable, preserving the relative order of equal elements. The trade-off is O(n) auxiliary space for the merge buffer. The repository identifies this as the algorithm used by Collections.sort() for object arrays.

Heap Sort (堆排序) constructs a max-heap from the input, then repeatedly extracts the maximum element and rebuilds the heap. It achieves O(n log n) time in all cases and sorts in-place with O(1) extra space. However, it is not stable and suffers from poor cache locality compared to Quick Sort.

Shell Sort (希尔排序) generalizes insertion sort by comparing elements separated by a gap sequence that decreases over time. The repository marks this entry as TODO, indicating the documentation is incomplete. When implemented, it typically yields O(n log n) to O(n^(3/2)) complexity depending on the gap sequence, with O(1) space usage.

Linear Time Non-Comparison Sorts

These algorithms exploit specific data constraints to achieve O(n) performance.

Counting Sort (计数排序) counts occurrences of each distinct value, computes prefix sums to determine positions, then constructs the output array. It requires integer keys in a limited range k, running in O(n + k) time with O(k) space. The repository notes this is efficient when k is not significantly larger than n.

Bucket Sort (桶排序) distributes elements into a fixed number of buckets, sorts each bucket individually (often with insertion sort), then concatenates the results. It achieves O(n + k) average-case time where k is the number of buckets, using O(n + k) space. Performance degrades if elements cluster into few buckets.

Radix Sort (基数排序) processes digits from least-significant to most-significant, using a stable sub-routine (typically counting sort) for each digit position. It runs in O(d · (n + k)) time where d is the number of digits and k the digit range, requiring O(n + k) auxiliary space.

Searching Algorithms

The repository documents the fundamental searching strategy for sorted collections in the same README.md section.

Binary Search

Binary Search (二分查找) operates on sorted arrays by repeatedly dividing the search interval in half. It compares the target value to the middle element; if unequal, it eliminates the half where the target cannot exist and continues searching the remaining half.

According to the repository documentation in README.md, this algorithm achieves O(log n) time complexity with O(1) space when implemented iteratively, or O(log n) space for recursive implementations due to call stack usage. The repository emphasizes that binary search requires the input to be pre-sorted and is the standard approach for lookup operations in static sorted datasets.

Java Implementation Details

The repository includes a dedicated section Java 中的排序工具 that explains how the standard library implements these algorithms.

Arrays.sort vs Collections.sort

Arrays.sort for primitive arrays (int[], double[], etc.) uses a Dual-Pivot Quick Sort algorithm tuned for performance on primitive data. This provides O(n log n) average-case performance but is not stable, as stability is irrelevant for primitives without identity.

For object arrays (Object[]), Arrays.sort delegates to TimSort, a hybrid of merge sort and insertion sort that provides O(n log n) performance while maintaining stability. This preserves the relative order of equal elements, which is critical when sorting complex objects by multiple fields.

Collections.sort for List objects delegates to List.sort(), which also uses TimSort by default. The repository notes that both utility methods achieve optimal O(n log n) performance for general-purpose sorting while handling stability requirements appropriately for object types.

Practical Code Examples

Below are concise Java implementations demonstrating the representative algorithms documented in the repository. These examples illustrate the core mechanics while remaining readable for educational purposes.

Quick Sort Implementation

This in-place recursive implementation reflects the divide-and-conquer strategy described in the repository's 快速排序 section:

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

Merge Sort Implementation

This top-down approach demonstrates the stable merging process documented in the 归并排序 section:

public static void mergeSort(int[] a, int[] aux, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, aux, lo, mid);
    mergeSort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
    System.arraycopy(a, lo, aux, lo, hi - lo + 1);
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (aux[i] <= aux[j]) a[k] = aux[i++];
        else a[k] = aux[j++];
    }
}

Binary Search Implementation

This iterative version reflects the O(log n) approach described in the 二分查找 section:

public static int binarySearch(int[] a, int key) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Using Java Standard Library Sorts

The repository emphasizes leveraging built-in utilities for production code:

int[] primitives = {5, 2, 9, 1};
Arrays.sort(primitives);               // Dual-Pivot QuickSort for primitives

List<String> list = Arrays.asList("delta", "alpha", "charlie");
Collections.sort(list);                // TimSort for objects, stable

Architectural Considerations

When applying these algorithms from the architect-awesome repository to production systems, consider these engineering trade-offs documented in the source analysis.

Complexity Trade-offs

The O-notation landscape directly impacts scalability. Quick Sort and Merge Sort provide O(n log n) average-case performance suitable for large datasets, while O(n²) algorithms like Selection Sort and Bubble Sort remain viable only for small arrays (n < 50) or educational purposes.

Stability Requirements

For multi-field sorting (e.g., sorting database records by age then by name), stability preserves the relative order of equal keys. Only Merge Sort, TimSort (used in Collections.sort), Counting Sort, and Insertion Sort guarantee stability. Quick Sort and Heap Sort are inherently unstable.

In-Place vs. Auxiliary Space

High-throughput services must balance memory constraints against performance guarantees:

• In-place algorithms (Quick Sort, Heap Sort, Selection Sort) use O(1) extra space, reducing GC pressure
• Auxiliary-space algorithms (Merge Sort, Radix Sort, Counting Sort) require O(n) or O(k) additional memory but provide stable sorting or linear time guarantees

Search-First Strategy

Binary Search requires pre-sorted data and provides O(log n) lookup. If your system performs frequent insertions interleaved with searches, maintaining a sorted array becomes expensive (O(n) per insertion). In such cases, the repository suggests considering balanced tree structures (e.g., Red-Black trees) to maintain O(log n) operations without explicit re-sorting.

Summary

• The architect-awesome repository documents twelve sorting algorithms and binary search in README.md under the 常用算法 section, providing time/space complexity for each implementation.
• Quick Sort and Merge Sort serve as the primary O(n log n) solutions, with Quick Sort favoring in-place memory usage and Merge Sort guaranteeing stability.
• Binary Search delivers O(log n) lookup performance but requires sorted input and offers O(1) space when implemented iteratively.
• Java's standard library implements Dual-Pivot QuickSort for primitives (Arrays.sort) and TimSort for objects (Collections.sort), both achieving O(n log n) average-case performance while handling stability appropriately.

Frequently Asked Questions

What is the difference between Quick Sort and Merge Sort in the architect-awesome repository?

Quick Sort (快速排序) uses an in-place partitioning strategy with O(log n) stack space, offering excellent cache performance but no stability guarantees. Merge Sort (归并排序) requires O(n) auxiliary space for merging but guarantees stability and consistent O(n log n) performance regardless of input distribution. The repository recommends Quick Sort for primitive arrays where memory is constrained and Merge Sort when stability is required for object sorting.

When should I use Binary Search according to the architect-awesome documentation?

The repository documents Binary Search (二分查找) as optimal for static sorted datasets where lookup performance is critical. It achieves O(log n) time complexity with O(1) space when implemented iteratively. However, the documentation implies that if your system requires frequent insertions alongside searches, maintaining a sorted array for binary search becomes inefficient due to O(n) insertion costs, suggesting balanced tree structures as alternatives.

Why does Java's Arrays.sort use different algorithms for primitives versus objects?

According to the Java 中的排序工具 section in README.md, Arrays.sort for primitives uses Dual-Pivot Quick Sort, which is faster and requires no stability since primitive values lack identity. For object arrays, it uses TimSort (a hybrid of Merge Sort and Insertion Sort) to guarantee stability, ensuring that equal elements maintain their original relative order—a critical requirement when sorting objects by multiple fields or keys.

Which sorting algorithm from architect-awesome is best for large datasets with limited memory?

The repository identifies Heap Sort (堆排序) and Quick Sort (快速排序) as the optimal choices for memory-constrained environments. Heap Sort guarantees O(n log n) time with O(1) auxiliary space and consistent performance regardless of input distribution. Quick Sort offers better cache locality and average-case speed but risks O(n²) worst-case behavior without randomized pivot selection. For guaranteed O(n log n) performance with minimal memory, Heap Sort is the conservative choice documented in the repository.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}