chap internal sorting exercises using inductionprove that insertion sort will always produce sorted array write an insertion sort algorithm for integer key values howeverhere' the catchthe input is stack (not an array)and the only variables that your algorithm may use are fixed number of integers and fixed number of stacks the algorithm should return stack containing the records in sorted order (with the least value being at the top of the stackyour algorithm should be th( in the worst case the bubble sort implementation has the following inner for loopfor (int = - >ij--consider the effect of replacing this with the following statementfor (int = - > --would the new implementation work correctlywould the change affect the asymptotic complexity of the algorithmhow would the change affect the running time of the algorithm when implementing insertion sorta binary search could be used to locate the position within the first elements of the array into which element should be inserted how would this affect the number of comparisons requiredhow would using such binary search affect the asymptotic running time for insertion sort figure shows the best-case number of swaps for selection sort as th(nthis is because the algorithm does not check to see if the ith record is already in the ith positionthat isit might perform unnecessary swaps (amodify the algorithm so that it does not make unnecessary swaps (bwhat is your prediction regarding whether this modification actually improves the running time(cwrite two programs to compare the actual running times of the original selection sort and the modified algorithm which one is actually faster recall that sorting algorithm is said to be stable if the original ordering for duplicate keys is preserved of the sorting algorithms insertion sortbubble sortselection sortshellsortquicksortmergesortheapsortbinsortand radix sortwhich of these are stableand which are notfor each onedescribe either why it is or is not stable if minor change to the implementation would make it stabledescribe the change