sorts

insertion sort

outer loop iterates through array starting from 1st index (j) to length-1, inner loop starts from 0 index (i)to length-2; if i>j greater insert at i position

in place stable

O(n)(best case) On^2 (worst case)

merge sort

split array into half until you reach 1 element array; compare on element arrays and combine

stable, in place

best and worse O(n log n)

heap sort

in place, (shrinks at front, sorted region grows at the tail) not stable (long distance swap reorders equal keys)

predictable but slower in practice

(n log n) worst case

quick sort

(lomuto scheme is quick sort but pivot is last element)

choose [last element] as pivot point, iterate through array and compare elements to pivot point. if j <= p, increase i by 1 and swap i and j

in place, not stable

best(n log n) worst case(n^2)

usually the fastest in practice