Week 11 Sorting and Effectiency

    During this week's lecture , Danny has introduced us two extra sorting algorithm ——merge sort and quick sort. The idea of quick sort is to select an item out of the data as a pivot(most of algorithm picks the first item). Then partition the data/list into two halves: items that are less than the pivot and the items that are greater than the pivot . than we can rearrange the list to get the right position of the pivot item we selected , select a new pivot and repeat the partition after that . This is the basic idea of a quick sort. it is a  fairly fast sorting technique. The best case run time for quick sort is O(n). and the worst case is O(nlogn). this is also one interesting idea pops up during the Wednesdays lecture. Since we know what the worst case of quick sort looks like. we can edit/ change our algorithm to avoid such situation by instead of choosing the first item on the list as pivot, now we  randomly pick out pivot item .
    The second sort technique that has been introduced is merge sort . it  splits the list in two halves and sorts two halves individually then merge two sorted halves. merge sort seems like it taking a lot steps to sort a small sized list. However , in a lag sized list . it performs just fine the worst case is same as quick sort O（nlogn)