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.




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

Recommended from Medium

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

Apache Hudi: Basic CRUD operations

Stream API in Java

Coding comprehension

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kevin Valias

Kevin Valias

More from Medium

My First Medium

Getting That Second Developer Job

5 Videos Junior Web Developers Should Watch

Image shows a boy in front of a computer.

Use These 6 Projects To Get Started as a Back-End Developer