Strategies for sorting

A sorting algorithm is a method of arranging a list of items in a certain order (ascending or descending).
The efficiency of a sorting algorithm depends on its time complexity in best, average and worst-case scenarios, and also its space complexity.
Some sorting algorithms are comparison sorts that work by comparing elements, while others are not.

Bubble Sort repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed.
Insertion Sort builds the sorted array one item at a time. It is much less efficient on large lists than other sorting algorithms like quicksort, heapsort, or merge sort.
Selection Sort is noted for its simplicity. It has an O(n^2) time complexity, which makes it inefficient on large lists, and generally performs worse than other quadratic sorting algorithms.
Merge Sort is a Divide and Conquer algorithm. It divides the array into equal halves and then combines them in a sorted manner.
Quicksort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.

To analyse a sorting algorithm, consider its time complexity in different scenarios (best, worst, and average), as well as its space complexity.
Use Big O Notation to express these complexities. This will determine how efficient or performant the algorithm is for large lists of data.

Implement sorting algorithms in practical code, carefully following the algorithm’s steps.
Use a variety of data to test sorting algorithms, including both random and ordered lists. Also test the algorithms with edge cases, such as an empty list or a list with duplicate items.

Look for ways to improve the time and space complexity of sorting algorithms. This might involve borrowing techniques from other algorithms or applying data structures effectively.
For example, Heap Sort is an example of an optimised sorting algorithm that leverages the properties of heaps to perform efficient sorting.
Realise that optimisation involves trade-offs: a more efficient sort might require more complex code, or a greater understanding of data structures.