Sorting algorithms aren't usually tested alone. They are often paired with another problem type and the goal is to really see if you're able to think about the algorithms in a wider context
Traverse from left to right, swap element with neighbor is neighbor is less than element
Repeat till no more swaps are needed
Invariant: after every iteration, the largest elements are arranged at the end in ascending order
Traverse from left to right, maintaining a “sorted” section in the front of the array
Every iteration, we seek the next smallest element in the “unsorted” section and insert to the front
Traverse from left to right
When encountering a number less than the current element, we move backwards, finding elements before the current element that is greater than the number
Repeat till a smaller number found, and then swap the elements into position
Break up the array into half and merge at the end
Stop breaking it up once only 1 element is left
Invariant: the leftmost set of elements will be sorted before the rightmost
# [left, right)defmerge_sort(arr,left,right):if left == right:return arr[left]elif left < right: mid = left + (right - left) //2 left_merged =merge_sort(arr, left, mid)# [left, mid) right_merged =merge_sort(arr, mid, right)# [mid, right)returnmerge(left_merged, right_merged)defmerge(a,b): c = [] i, j =0,0while i <len(a)and j <len(b):if a[i]< b[j]: c.append(a[i]) i +=1else: c.append(b[j]) j +=1 idx, remaining = (i, a) if i <len(a)else (j, b)for k inrange(idx, len(remaining)): c.append(remaining[k])return c
Pick a pivot, partition array around pivot value, and repeat for all halves till 1 element