Sorting Algorithm Evaluation

settings menu
format_line_spacing Insertion Sort
bolt Quick Sort
call_split Merge Sort

Algorithm Visualization

Step: 0
Select a dataset to start

Performance Comparison

Intuitively compare algorithm performance differences across different scales and sorting states on a logarithmic scale

Dataset Insertion Sort (ms) Quick Sort (ms) Merge Sort (ms)
1000places_sorted 0.7209 7.1515 0.4774
1000places_random 2.4313 0.2031 0.2206
10000places_sorted 0.2419 171.752 1.5111
10000places_random 73.7628 2.008 3.2734

* Note: Measured in milliseconds, lower values indicate better performance

Algorithm Details

Insertion Sort

Insertion sort is a simple and intuitive sorting algorithm. It works by building a sorted sequence and for unsorted data, it scans from the back to the front in the sorted sequence to find the appropriate position and insert.

Time Complexity

Best Case: O(n)

Average Case: O(n²)

Worst Case: O(n²)

Space Complexity

O(1)

private static void insertionSort(String[] arr) {
    for (int i = 1; i < arr.length; i++) {
        String key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j].compareTo(key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Application Scenario Analysis

check_circle_outline Small Datasets

Insertion sort performs well and is simple to implement for small datasets.

check_circle_outline Nearly Sorted Data

When data is already close to being sorted, insertion sort approaches linear time performance.

check_circle_outline Memory Constrained Environments

With O(1) space complexity, it's very suitable for embedded systems and other memory-constrained environments.