Comparison of sorting algoritms

Which sorting algorithm makes minimum number of memory write ?

Cycle Sort (an Unstable comparison sorting algorithm) is optimized to make minimum number of writes. It writes each value at the most once if it is not already at its right position. If the element is already at the position where it will be in the final output, then it is never written.

Out of the common stable-sorting algorithms, Selection Sort makes the minimum number of writes.

Number of writes are important if we are using a memory where each write to memory reduces the life of memory (like Flash memory).

Which Sorting Algorithm is best suited for External Sorting ?

External sorting means that not entire data is in the RAM. (Imagine sorting an array half of which is on hard disk). The challenge of external sorting is not to reduce the CPU processing time (Order complexities) but to reduce the number of reads/writes from the hard disk. Merge Sort is a very good choice for external sorting.

Which sorting Algorithm will you use to sort an array which is almost sorted ?

The choice is Insertion Sort. If the array is almost sorted, Insertion sort tends to give its best case (O(n)) performance.

Compare the time & space complexities of Sorting algorithms

The below image provides a comparative study of all the sorting algorithms in terms of Time complexity, Extra space taken, whether the algorithm provides stable or unstable sorting and whether or not it is Comparison Sorting algorithm.

Meaning of the terms are as follows:

Comparison v/s Non-Comparison Sorting:

If while sorting we compare the elements then the algorithm is called Comparison sorting algorithm. If the algorithm sorts the array without comparing the elements, then it is called non-comparison sorting algorithm.

Stable v/s UnStable Sorting:

If the relative order of two equal elements is same in the sorted array as it was in the original array, then the algorithm used for sorting is stable sorting algorithm else it is unstable sorting algorithm.

Space Complexity:

The amount of extra space used with respect to the number of elements in the array. O(1) means that a constant amount of extra space is used irrespective of the number of elements in the array.

Time Complexity:

Time used with respect to the number of elements in the array.