although general analysis of the shell sort is well beyond the scope of this textwe can say that it tends to fall somewhere between (nand ( )based on the behaviour described above by changing the incrementfor example using ( and so on) shell sort can perform at ( self check given the following list of numbers[ which answer illustrates the contents of the list after all swapping is complete for gap size of [ [ [ [ the merge sort we now turn our attention to using divide and conquer strategy as way to improve the performance of sorting algorithms the first algorithm we will study is the merge sort merge sort is recursive algorithm that continually splits list in half if the list is empty or has one itemit is sorted by definition (the base caseif the list has more than one itemwe split the list and recursively invoke merge sort on both halves once the two halves are sortedthe fundamental operationcalled mergeis performed merging is the process of taking two smaller sorted lists and combining them together into singlesortednew list figure shows our familiar example list as it is being split by merge_sort figure shows the simple listsnow sortedas they are merged back together the merge_sort function shown below begins by asking the base case question if the length of the list is less than or equal to onethen we already have sorted list and no more processing is necessary ifon the other handthe length is greater than onethen we use the python slice operation to extract the left and right halves it is important to note that the list may not have an even number of items that does not matteras the lengths will differ by at most one def merge_sort(a_list)print("splitting "a_listif len(a_list mid len(a_list/ left_half a_list[:midright_half a_list[mid: merge_sort(left_halfmerge_sort(right_half sorting and searching