Insertion Sort
Time Complexity - O(n^2) || Space Complexity - O(1) We maintain array like this - [sorted portion | unsorted portion] (same as selection sort) Now in every iteration of i , we take first element of unsorted portion and try to insert it in sorted portion at it's correct place by comparing the currently picked first element of unsorted and swapping it repeteadly with previous elements in sorted portion [starting from last element of sorted portion] and swapping them according to our need whether we want to sort in increasing or decreasing order. While doing the above swapping, remember we are moving from last to first element of sorted portion and swapping them. If sorting in increasing order, if we find any element before swapping to be less than the current element, we do not swap and break from the inner loop of j and continue our next iteration of i loop. Insertion sort is best sorting algorithm if we are continuously getting new inputs and we have to place the new input ...