Sort

Sort functions arrange elements in a specified order.

Python Example

Python sort details can be found here.

Python sort uses the Timsort algorithm, which is a hybrid sort derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. The Big O Notation time complexity of Timsort is O(n log(n)), but this can vary depending on the level of sort that already exists in the input data.

# Use the built-in list sort() function that sorts the input list in place.
sample_list = [5, 2, 6, 7]
sample_list.sort( )
print(sample_list )

# Use the built-in list sorted() function that creates a new sorted list.
sample_list = [5, 2, 6, 7]
sorted_sample_list = sorted(sample_list)
print(sorted_sample_list)

Sorting Algorithms

If you don't want to use a built-in sort function and you're going to implement your own sort function, there's a large list of sorting algorithms to choose from.  Factors to consider in choosing a sort algorithm include:

  • Speed of the algorithm for the best, average and worst sort times. Most algorithms have sort times characterized by Big O functions of O(n), O(n log(n)) or O(n^2).

  • The relative importance of the best, average and worst sort times for the sort application.

  • Memory required to perform the sort.

  • Type of data to be sorted (e.g., numbers, strings, documents).

  • The size of the data set to be sorted.

  • The need for sort stability (preserving the original order of duplicate items).

  • Distribution and uniformity of values to be sorted.

  • Complexity of the sort algorithm.

For a comparison of sorting algorithms based on these and other values see: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Here's a quick reference for the major algorithms:

  • Exchange Sorts: based on swapping items

    • Bubble sort: for each pair of indices, swap the items if out of order, loop for items and list.

    • Cocktail sort: variation of bubble sort, passes alternately from top to bottom and bottom to top.

    • Comb sort: variation of bubble sort, selective swap of values

    • Gnome sort: also called the stupd sort, moves values back to just above a value less than it

    • Odd-even sort: developed originally for use with parallel processors, examines odd-even pairs and orders them, alternates pairs until list is ordered

    • Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Repeat. Often the method of choice. One of the fastest sort algorithms

  • Hybrid Sorts: mixture of sort techniques

    • Flashsort: Used on data sets with a known distribution, estimates used for where an element should be placed

    • Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level

    • Timsort: adaptative algorithm derived from merge sort and insertion sort. 

  • Insertion sorts: builds the final sorted array one item at a time

    • Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there

    • Library sort: like library shelves, space is created for new entries within groups such as first letters, space is removed at end of sort

    • Patience sorting: based on the solitaire card game, uses piles of "cards"

    • Shell sort: an attempt to improve insertion sort

    • Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list

    • Cycle sort: in-place with theoretically optimal number of writes

  • Merge sorts: takes advantage of the ease of merging already sorted lists into a new sorted list

    • Merge sort: sort the first and second half of the list separately, then merge the sorted lists

    • Strand sort: repeatedly pulls sorted sublists out of the list to be sorted and merges them with the result array

  • Non-comparison sorts

    • Bead sort: can only be used on positive integers, performed using mechanics like beads on an abacus

    • Bucket sort: works by partitioning an array into a number of buckets, each bucket is then sorted individually using the best technique, the buckets are then merged

    • Burstsort: used for sorting strings, employs growable arrays

    • Counting sort: sorts a collection of objects according to keys that are small integers

    • Pigeonhole sort: suitable for sorting lists of elements where the number of elements and number of possible key values are approximately the same, uses auxiliary arrays for grouping values

    • Postman sort: variant of Bucket sort which takes advantage of hierarchical structure

    • Radix sort: sorts strings letter by letter

  • Selection sorts: in place comparison sorts

    • Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list

    • Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list

    • Smoothsort

  • Other

  • Unknown class

References