Selection sort repeatedly chooses a minimum element from the unprocessed collection and moves it to the next output position. After each step the output string prefix is sorted and no larger than any remaining element. Repeated linear minimum scans give quadratic worst-case time. A linked list implementation can detach and append existing nodes using constant auxiliary space while preserving duplicate elements. The sorted result is nondecreasing, not strictly increasing when duplicates occur.
Articles by others on the same topic
Selection Sort is a simple and intuitive comparison-based sorting algorithm. It works by dividing the input list into two parts: a sorted and an unsorted region. The algorithm repeatedly selects the smallest (or largest, depending on the order) element from the unsorted region and swaps it with the first unsorted element, effectively growing the sorted region and shrinking the unsorted region until the entire list is sorted.