in the second version of the listtwo merges are done for the lists of length two howevereach merge is done on one half the list the purple half is one mergethe green half includes the items that are in the second merge togetherthese two merges include all items again soat the second deepest level again at most items are merged in (ntime finallythe last merge is of all the items in yellow from the two sorted sublists this merge also takes (ntime since it merges all the items in the listresulting in the sorted list seen in the last version of the list sowhile merging is (noperationthe merges take place on sublists of the items in the list which means that we can count the merging at each level as (nand don' have to count each individual merge operation as (nsince there are log levels to the merge sort algorithm and each level takes (nto mergethe algorithm is ( log quicksort in sensethe quicksort algorithm is the exact opposite of the merge sort algorithm it is also the most widely used and one of the most efficient sorting algorithms known quicksort is again divide and conquer algorithm and is usually written recursively butwhere merge sort splits the list until we reach size of and then merges sorted liststhe quicksort algorithm does the merging first and then splits the list we can' merge an unsorted list insteadwe partition it into two lists what we want is to prepare the list so quicksort can be called recursively butif we are to be successfulthe two sublists must somehow be easier to sort than the original this preparation for splitting is called partitioning to partition list we pick pivot element think of quicksort partitioning list into all the items bigger than the pivot and all the elements smaller than the pivot we put all the bigger items to the right of the pivot and all the littler items to the left of the pivot once we have done thistwo things are truethe pivot is in its final location in the list the two sublists are now smaller and can therefore be quicksorted once the two sublists are sorted this will cause the entire list to be in sorted orderbecause the left will be the values ascending up to the pivotthe pivot is in the right spotand the values greater than the pivot will all be in their correct locationstoo quicksort is divide and conquer algorithm to get the best performancewe would like to divide the sequence right down the middle into two equal sized sequences this would mean that we would have to pick the value exactly in the middle to be the pivot since the pivot is used to divide the two lists unfortunately this isn' possible if we are to do it efficiently for quicksort to have ( log ncomplexitylike merge sortit must partition the list in (ntime we must choose pivot quickly and we must choose it well if we don' choose pivot close to the middlewe will not get the ( log ncomplexity we hope for it turns out that choosing random pivot from the list is good enough one way to guarantee random choice this copy belongs to 'acha