Bubble SortIterate through sequence, compare each element to right neighbor.Exchange adjacent elements if necessary.
Keep passing through sequence until no exchanges are required (up to N times).
Each pass causes largest element to bubble into place: 1st pass, largest; 2nd pass, 2nd largest, ...
Like inserting new card into a partially sorted hand by bubbling to left into sorted subarray; little less brute-force than bubble sort
add one element a[i] at a time
find proper position, j+1, to the left by shifting to the right a[i-1], a[i-2], ..., a[j+1] left neighbors, til a[j] < a[i]
move a[i] into vacated a[j+1]
After iteration i<n, a[1] ... a[i] are in sorted order, but not necessarily in final position