fortgeschrittene-sortierverfahren

Advanced Sorting

In short: More efficient sorting algorithms beyond the simple, easily understood but slow basic methods — developed to stay practically fast even for very large amounts of data.

In more detail: Methods like merge sort or quicksort use “divide and conquer”: the problem is broken down recursively into smaller subproblems, these are sorted separately and then merged back together. This makes them grow significantly slower with the amount of data than simple quadratic methods like bubble sort.

In Depth

The efficiency gain over simple methods (bubble sort, insertion sort — both O(n²)) is enormous for larger amounts of data: O(n log n) instead of O(n²) means, for a million elements, the difference between a few seconds and potentially hours.

Merge sort repeatedly splits the list in the middle, until only individual elements remain (which are automatically “sorted”), and then merges them back together pairwise in sorted order:

function mergeSort(list):
    if LENGTH(list) <= 1:
        return list                    // base case of the recursion
    middle = LENGTH(list) / 2
    left = mergeSort(list[0:middle])   // recursive call on the left half
    right = mergeSort(list[middle:])   // recursive call on the right half
    return merge(left, right)          // merge two sorted halves

Merge sort is “stable” (elements with the same sort value keep their original order) and ALWAYS guarantees O(n log n), no matter how the input data is arranged — but it needs additional memory for the temporary sublists.

Quicksort instead picks a “pivot” element, splits the rest of the list into “smaller than pivot” and “larger than pivot”, and recursively sorts these two groups further:

function quickSort(list):
    if LENGTH(list) <= 1:
        return list
    pivot = choose_element(list)
    smaller = [x for x in list IF x < pivot]
    larger = [x for x in list IF x > pivot]
    return quickSort(smaller) + [pivot] + quickSort(larger)

Quicksort is on average even somewhat faster than merge sort (lower memory usage, usually better cache use), but has a weak point: with an unfavourable pivot choice (e.g. always the first element for an already sorted list), the runtime can fall back to O(n²) in the worst case — modern implementations therefore choose the pivot randomly or via a “median-of-three” approach, to make this worst-case scenario extremely unlikely in practice.

In practice, you rarely have to implement these algorithms yourself — the standard libraries of almost all languages already come with highly optimised sorting functions (e.g. a mix of several methods, depending on data size and type) that you simply call. Understanding what’s BEHIND them still matters, though, to be able to judge when sorting can become a performance bottleneck.

See also: Sorting, Recursion, Algorithms