# My Imutality#206

• Simple implementation
• Efficient for small data sets
• Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(n+d), where d is the number of inversions
• More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort: the average running time is n2/4, and the running time is linear in the best case
• Stable, i.e., does not change the relative order of elements with equal keys
• In-place, i.e., only requires a constant amount O(1) of additional memory space
• Online, i.e., can sort a list as it receives it
• Worst case performance: O(n2)
• Best case performance: O(n)
• Average case performance: O(n2)
• Worst case space complexity: O(n) total, O(1) auxiliary
1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying merge sort.
4. Merge the two sublists back into one sorted list.
1. A small list will take fewer steps to sort than a large list.
2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they’re already sorted.
• Worst case performance: O(n log n)
• Best case performance: O(n log n) typical
• Average case performance: O(n log n)
• Worst case space complexity: O(n) total, O(n) auxiliary
1. Pick an element, called the pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements 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 sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which are always sorted.
• At each iteration, all the elements processed so far are in the desired position: before the pivot if less than or equal to the pivot’s value, after the pivot otherwise.
• Each iteration leaves one fewer element to be processed.
• A base case is typically a problem that is small enough to solve directly.
• In the `factorial` algorithm the base case is n=1.
• A change of state means that some data that the algorithm is using is modified.
• Usually the data that represents our problem gets smaller in some way.
• In the `factorial` n decreases.

--

--

--

## More from Kevin Valias

Love podcasts or audiobooks? Learn on the go with our new app.

## Data Observability in Practice Using SQL, Part II: Schema & Lineage ## AWS CloudFront Setup ## 10 Years of WebRTC — 9 Successful WebRTC Applications ## Amortised analysis in the nutshell ## FileMaker DevCon 2018 Highlights ## Stream API in Java ## Coding comprehension ## My First Medium ## Getting That Second Developer Job ## 5 Videos Junior Web Developers Should Watch ## Use These 6 Projects To Get Started as a Back-End Developer 