From the free course Java Programming and Algorithmic Thinking Fundamentals on Lykke

Searching and Sorting Algorithms

Key concepts: Binary Search · Selection Sort · Insertion Sort · Merge Sort · Algorithm Complexity Analysis

Implementation and performance analysis of fundamental algorithms for organizing and finding data.

Searching and Sorting Algorithms

In the realm of computer science, the ability to organize and retrieve data efficiently is not merely a convenience—it is a fundamental requirement for scalable systems. Whether you are building a search engine, a financial trading platform, or a simple mobile application, the choice of searching and sorting algorithms dictates the performance boundaries of your software. This section explores the mechanics, mathematical foundations, and practical implementations of the industry's most essential algorithms, alongside the analytical tools used to measure their efficacy.

Algorithm Complexity Analysis

Before examining specific algorithms, we must establish a rigorous framework for evaluation. Algorithm Complexity Analysis is the study of how the resource requirements of an algorithm (typically time and memory) scale as the size of the input data, denoted as $n$, increases.

The Big O Notation

We use Big O Notation to describe the "asymptotic upper bound" of an algorithm. It allows us to ignore constant factors and hardware-specific variations, focusing instead on the growth rate.

Definition: An algorithm is $O(f(n))$ if there exist constants $c$ and $n_0$ such that the execution time $T(n) \le c \cdot f(n)$ for all $n > n_0$.

Common Complexity Classes

Notation Name Description Example
$O(1)$ Constant Time remains the same regardless of $n$. Accessing an array element by index.
$O(\log n)$ Logarithmic Time increases linearly as $n$ increases exponentially. Binary Search.
$O(n)$ Linear Time increases in direct proportion to $n$. Linear Search.
$O(n \log n)$ Linearithmic The standard for efficient sorting. Merge Sort.
$O(n^2)$ Quadratic Time increases with the square of $n$. Selection Sort, Insertion Sort.
$O(2^n)$ Exponential Time doubles with each additional element. Recursive Fibonacci (naive).

Why Complexity Matters

Consider an input size of $n = 1,000,000$. An $O(n)$ algorithm might take a fraction of a second, while an $O(n^2)$ algorithm would perform $1,000,000,000,000$ operations, potentially taking hours or days on standard hardware. As a professor would emphasize: Efficiency is not about saving microseconds; it is about making the impossible possible.


Linear Search

Linear Search (or Sequential Search) is the most intuitive method for finding a target value within a collection. It involves examining each element of the array one by one until the target is found or the end of the array is reached.

How it Works

  1. Start at the first element (index 0).
  2. Compare the current element with the target key.
  3. If they match, return the current index.
  4. If they do not match, move to the next index.
  5. If the end of the array is reached without a match, return -1.

Java Implementation

public class SearchUtils {
    /**
     * Performs a linear search on an integer array.
     * @param a the array to search
     * @param key the value to find
     * @return the index of the key, or -1 if not found
     */
    public static int linearSearch(int[] a, int key) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == key) {
                return i; // Found the key
            }
        }
        return -1; // Key not present
    }
}

Complexity Analysis

  • Best Case: $O(1)$ (The key is the first element).
  • Worst Case: $O(n)$ (The key is the last element or not present).
  • Average Case: $O(n/2)$, which simplifies to $O(n)$.

Common Pitfalls: Linear search is inefficient for large datasets. However, it is the only option if the data is unsorted and we have no additional information about the structure.


Binary Search

Binary Search is a vastly more efficient algorithm that operates on the "divide and conquer" principle. However, it carries a strict prerequisite: the array must be sorted.

The Logic of Halving

Imagine searching for a name in a physical phone book. You don't start at page one; you open to the middle. If the name you seek is alphabetically "less than" the names on the page, you discard the entire right half of the book and repeat the process with the left half.

How it Works

  1. Maintain two pointers, low and high, representing the current search range.
  2. Calculate the middle index: mid = low + (high - low) / 2.
  3. Compare a[mid] with the key:
    • If a[mid] == key, return mid.
    • If a[mid] < key, set low = mid + 1 (search the right half).
    • If a[mid] > key, set high = mid - 1 (search the left half).
  4. Repeat until low > high.

Java Implementation

public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Prevents integer overflow
        if (key < a[mid]) {
            high = mid - 1;
        } else if (key > a[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Mathematical Derivation of Complexity

In each step, we reduce the search space by half. After $k$ steps, the remaining search space is $n / 2^k$. The algorithm terminates when the search space is reduced to 1. $$n / 2^k = 1 \implies n = 2^k \implies k = \log_2 n$$ Thus, the complexity is $O(\log n)$.


Selection Sort

Selection Sort is a simple, comparison-based sorting algorithm. It maintains two sub-arrays in a given array: one which is already sorted and the other which is unsorted.

Mechanics

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted sub-array is picked and moved to the beginning of the sorted sub-array.

Worked Example

Array: [64, 25, 12, 22, 11]

  1. Find the min in [64, 25, 12, 22, 11]. It's 11. Swap with 64. Result: [11, 25, 12, 22, 64]
  2. Find the min in [25, 12, 22, 64]. It's 12. Swap with 25. Result: [11, 12, 25, 22, 64]
  3. Find the min in [25, 22, 64]. It's 22. Swap with 25. Result: [11, 12, 22, 25, 64]
  4. Array is sorted.

Java Implementation

public static void selectionSort(double[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) {
                minIdx = j;
            }
        }
        // Swap the found minimum element with the first element
        double temp = a[minIdx];
        a[minIdx] = a[i];
        a[i] = temp;
    }
}

Complexity and Performance

  • Time Complexity: $O(n^2)$ in all cases (best, average, worst) because the nested loops always execute.
  • Space Complexity: $O(1)$ (In-place).
  • Pitfall: It is inefficient on large lists and generally performs worse than insertion sort.

Insertion Sort

Insertion Sort works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

How it Works

  1. Iterate from index 1 to n-1.
  2. Compare the current element (key) to its predecessor.
  3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Java Implementation

public static void insertionSort(double[] a) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        double key = a[i];
        int j = i - 1;

        // Move elements of a[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}

Variations and Extensions

Insertion sort is highly efficient for nearly sorted data. In such cases, the inner while loop rarely runs, leading to a near $O(n)$ performance. This makes it a popular choice as a "base case" for more complex algorithms like Timsort or Quicksort.

Feature Selection Sort Insertion Sort
Best Case $O(n^2)$ $O(n)$
Swaps $O(n)$ $O(n^2)$
Stability Usually Unstable Stable
Use Case When memory writes are costly Small or nearly sorted arrays

Merge Sort

Merge Sort is a sophisticated, recursive algorithm that exemplifies the "Divide, Conquer, and Combine" strategy. It is significantly faster than selection or insertion sort for large datasets.

The Divide and Conquer Strategy

  1. Divide: Divide the unsorted list into $n$ sub-lists, each containing one element (a list of one element is considered sorted).
  2. Conquer: Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sub-list remaining.

The Merge Step

The core of the algorithm is the merge() function, which takes two sorted arrays and combines them into a single sorted array.

Java Implementation

public class MergeSort {
    public static void sort(double[] a) {
        if (a.length <= 1) return;
        double[] aux = new double[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private static void sort(double[] a, double[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);       // Sort left half
        sort(a, aux, mid + 1, hi);   // Sort right half
        merge(a, aux, lo, mid, hi);  // Merge results
    }

    private static void merge(double[] a, double[] aux, int lo, int mid, int hi) {
        // Copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // Merge back to a[]
        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[j] < aux[i])   a[k] = aux[j++];
            else                        a[k] = aux[i++];
        }
    }
}

Complexity Analysis

Merge sort consistently performs at $O(n \log n)$ time complexity.

  • Log n levels: The array is split in half $\log n$ times.
  • N work per level: At each level of the recursion tree, the total number of comparisons and movements is proportional to $n$.
  • Space Complexity: Unlike the previous sorts, Merge Sort requires $O(n)$ additional space for the auxiliary array.

Comparative Summary of Sorting Algorithms

Choosing the right algorithm depends on the specific constraints of your environment (e.g., memory limits, data size, initial order).

Algorithm Best Time Avg Time Worst Time Space Stable?
Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ No
Insertion Sort $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Yes
Merge Sort $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ Yes

Key Insights for Engineers

  1. Stability: A sort is stable if it preserves the relative order of equal elements. This is crucial when sorting objects by multiple criteria (e.g., sorting a list of transactions by date, then by amount).
  2. In-place: An algorithm is in-place if it requires only a constant amount of extra memory ($O(1)$). Selection and Insertion sort are in-place; Merge Sort is not.
  3. Adaptive: An algorithm is adaptive if its performance improves when the input is partially sorted. Insertion sort is the quintessential adaptive algorithm.

Common Pitfalls in Implementation

  • Integer Overflow: In Binary Search, calculating mid = (low + high) / 2 can cause an overflow if low + high exceeds Integer.MAX_VALUE. Use low + (high - low) / 2 instead.
  • Off-by-One Errors: Pay close attention to loop boundaries (e.g., i < n vs i <= n) and the calculation of the mid point in recursive calls.
  • Recursion Depth: For extremely large arrays, recursive algorithms like Merge Sort can trigger a StackOverflowError if the recursion depth is too great, though this is rare for $O(\log n)$ depth.
Searching and Sorting Algorithms - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
Searching and Sorting Algorithms - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
Searching and Sorting Algorithms - Java Programming and Algorithmic Thinking Fundamentals - diagram 2
Searching and Sorting Algorithms - Java Programming and Algorithmic Thinking Fundamentals - diagram 2

Source Materials

Study Java Programming and Algorithmic Thinking Fundamentals on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Java Programming and Algorithmic Thinking Fundamentals · Browse more course pages