sorting-rearranging a collection of items into increasing or decreasing order-is a common problem in computing. Sorting is used to preprocess the collection to make searching faster (binary search through an array), as well as to identify items that are similar (e.g., students are sorted on test scores). Naive sorting algorithms run in 8 time. There are O(n^2) of sorting algorithms which run in O(nlogn) time-Mergesort, Heapsort, and Quicksort are examples. Each has its advantages and disadvantages: for example, Heapsort is in-place but not stable; Mergesort is stable but not in-place.

Parameters

Stability: A sorting algorithm is stable if it preserves the relative order of equal elements after sorting.

In place: A sorting algorithm is in-place if it sorts using only O(1) auxiliary memory (not counting the array that needs to be sorted).

Best case complexity: A sorting algorithm has a best-case time complexity of O(T(n)) if its running time is at least T(n) for all possible inputs.

Average case complexity: A sorting algorithm has an average case time complexity of O(T(n)) if its running time, averaged over all possible inputs, is T(n).

Worst-case complexity: A sorting algorithm has a worst-case time complexity of O(T(n)) if its running time is atmost T(n).

In my next post, I will give detailed information about various sorting algorithms and their advantages and disadvantages.