Sorting a process of ordering a list of elements in either ascending or descending order. Sorting can be divided into two categories:
- Internal sorting
- External sorting
Internal sorting takes place in the main memory of the computer. Internal sorting can take advantages of the Random access nature of the main memory. Elements to be stored are stored in an integers array. These elements can be stored using one of the various algorithms available.
External sorting is carried on secondary storage. External sorting becomes a necessity if the numbers of elements to be stored is too large to fit in the main memory. External sorting should always take into account that movement of data between secondary storage and main memory is the best done by moving a block of contiguous elements.
- Simple sorting algorithms like bubble sort, insertion sort takes O(n2) time to sort n elements.
- More complicated algorithms like quick sort, merge sort, heap sort take O(n logn) times to sort n elements.
- Sorting elements like bubble sort, insertion sort, merge sort are stable. Whereas quick sort and heap sort are unstable sort. A sorting algorithm is said to be stable if after storing, identical elements appear in the same sequence as in the original unsorted list.
