One Pager Cheat Sheet

• If you are new to sorting, come up with your own algorithm first and then compare it to the fundamental sorting techniques to gain important insights into how to sort arrays, improve an algorithm and when to apply a certain sort procedure.
• Bubble sort starts by dividing the array into a sorted and unsorted sub-array, and compares consecutive items to sort them by "bubbling down" heavier items and "bubbling up" lighter items.
• Bubble Sort has a time complexity of O(n^2), as it must compare all consecutive pairs and perform a swap operation for each comparison, with a total of n * (n-1) / 2 comparisons necessary.
• Bubble sort is a very special algorithm which is one of the few sorting algorithms that tells you when an array is sorted and can stop running further passes if the array is already sorted, thus having an O(n) best-case complexity and an O(n${}^2$) worst-case complexity with an O(1) space complexity.
• Insertion Sort is an easy-to-implement algorithm that swaps items if needed in order to insert them in their correct place in the sorted sub-array.
• Insertion Sort has a worst-case time complexity of O(n$^2$), due to needing to iterate through the sorted sub-array and compare each element to each item before it in an O(n) operation.
• Insertion sort is an in place sorting algorithm which has time complexity of O(n) if the input is already sorted, and worst case time complexity of O(n$^2$) if the input is in descending order.
• If you know in advance that your array is almost sorted, then **both bubble sort and insertion sort would be very efficient**.
• Bubble sort is an in-place sorting algorithm with O(1) space complexity, making it an efficient method for sorting data.
• Insertion Sort has excellent `space complexity of O(1), requiring only constant extra space**.