Introduction

A sorting algorithm is an algorithm made up of a series of instructions that takes an array as input, performs specified operations on the array, sometimes called a list, and outputs a sorted array. Sorting algorithms are often taught early in computer science classes as they provide a straightforward way to introduce other key computer science topics like Big-O notation, divide-and-conquer methods, and data structures such as binary trees, and heaps. There are many factors to consider when choosing a sorting algorithm to use.

Properties of Sorting Algorithms

Time Complexity
Space Complexity
Stability : A sorting algorithm is stable if it preserves the original order of elements with equal key values

Useful Sorting Algorithms

Insertion Sort

Insertion sort is a comparison-based algorithm that builds a final sorted array one element at a time. It iterates through an input array and removes one element per iteration, finds the place the element belongs in the array, and then places it there.
Insertion sort can be improved by use binary search to find the position to insert.

Time Complexity(average, best, wrost) : O(n^2), O(n), O(n^2)
Space Complexity : O(1)
Binary Insertion Sort Time Complexity : O(nlog(n)) O(n) O(nlog(n))

Quick Sort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:

1. Pick an element, called a pivot, from the array.
2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

*the strategy to choose pivot is very important, which will affect the efficient of Quick Sort.

Time Complexity : O(nlog(n)), O(nlog(n)), O(n^2)
Space Complexity : O(nlog(n))

Merge Sort

Merge Sort is also a divide and conquer algorithm, the different with Quick Sort is its flow is TOP->BOTTOM->TOP. steps are:

1. Recursively divide a list into 2 sublist, for the sublist do the division until sublist only contain one element.
2. Recursively merge two sublist log(n) times, each merge processing will travel two sublist and put element into new list by order.

Time Complexity : O(nlog(n)), O(nlog(n)), O(nlog(n))
Space Complexity : O(n)