sortlisten

Sortlisten is the German term for lists whose elements are arranged according to a defined ordering criterion, such as numeric ascending order or lexicographic order. In computer science, a sorted list is a data structure that maintains its elements in nondecreasing (or nonincreasing) order. This ordering enables efficient iteration and supports faster search via binary search, at the cost of more expensive updates.

There are static and dynamic variants. A static sorted list is fixed after creation, while a dynamic sorted list preserves order during insertions and deletions, often by repositioning elements or by using a data structure designed for reordering.

Common implementations include array-based and linked-list-based structures, as well as more advanced forms. An array-based sorted list stores elements contiguously; search can use binary search (O(log n) time) but insertion or deletion requires shifting elements (O(n)). A sorted linked list allows O(1) insertion once the correct position is found, but search remains O(n). Balanced search trees, such as AVL trees or red–black trees, maintain sorted order with O(log n) time for search, insertion, and deletion, and support in-order traversal.

Applications include in-memory databases, indexing, and libraries or modules that require ordered iteration or range queries. Sorted lists are contrasted with unsorted collections that require full scans for lookups.

In German-language computing literature, Sortlisten is commonly used to refer to lists kept in sorted order, sometimes synonymous with sortierte Listen.