[ ]= with [ ]= these entries are in orderso nothing happens (note that these numbers have been compared before there is nothing in bubble sort that prevents it from repeating comparisonswhich is why it tends to be pretty slow!then it compares [ ]= and [ ]= these are not in orderso they have to be swappedgiving since we already know that [ contains the smallest itemwe leave it aloneand the second pass is finished note that now the second-smallest entry is in placetoo the algorithm now starts the third and final passcomparing [ ]= and [ ]= again these are out of order and have to be swappedgiving since it is known that [ and [ contain the correct items alreadythey are not touched furthermorethe third-smallest item is in place nowwhich means that the fourth-smallest has to be correcttoo thus the whole array is sorted it is now clear that bubble sort can be implemented as followsfor +for - > -if [ja[ - swap [jand [ - the outer loop goes over all positions that may still need to be swapped to the leftand the inner loop goes from the end of the array back to that position as is usual for comparison-based sorting algorithmsthe time complexity will be measured by counting the number of comparisons that are being made the outer loop is carried out times the inner loop is carried out ( ( times so the number of comparisons is the same in each casenamely - - = = - ( ii= ( ( ( thus the worst case and average case number of comparisons are both proportional to and hence the average and worst case time complexities are ( insertion sort insertion sort is (not surprisinglya form of insertion sorting it starts by treating the first entry [ as an already sorted arraythen checks the second entry [ and compares it with the first if they are in the wrong orderit swaps the two that leaves [ ], [ sorted then it takes the third entry and positions it in the right placeleaving [ ], [ ], [ sortedand so on more generallyat the beginning of the ith stageinsertion sort has the entries [ ] [ - sorted and inserts [ ]giving sorted entries [ ], [ifor the example starting array insertion sort starts by considering [ ]= as sortedthen picks up [ and 'inserts itinto the already sorted arrayincreasing the size of it by since [ ]= is smaller than [ ]= it has to be inserted in the zeroth slot