o Compare two adjacent items, arrange them in order relative to each other
Then move on to compare the next two adjacent items
Next irritation, last item ignored
1. def bubble_sort(L):
2. '''Sort the items in L in non-descending order.'''
4. # Do one major pass/iteration through the the unsorted part of the list
5. # (the part from the beginning to i spots from the end). Sink the largest
6. # value in that part of the list to the end of that part of the list.
8. for i in range(len(L)):
9. for j in range(len(L) - i - 1):
10. if L[j] > L[j + 1]:
11. L[j], L[j + 1] = L[j + 1], L[j]
12. return L
merge sort splits list into two sorted lists; compare the top two items, the smaller/lager is placed in the final list
o then compare the top two items again, the smaller/larger item is placed in the final list
o to split list into two sorted lists, use merge sort
o recursion call same function within a function
1. def merge(left, right):
2. '''Return the list made by merging sorted lists left and right.'''
3. result = 
4. i ,j = 0, 0
5. while i < len(left) and j < len(right):
6. if left[i] <= right[j]:
8. i = i + 1
11. j = j + 1
13. # One of the sublists has elements left over; the other is empty. Copying
14. # both does no harm, since the empty one will add nothing.
15. result += left[i:]