Sorting
Table of contents
Submit your solutions to the following questions as a PDF on Gradescope.
Stability
Give a crisp and concise English description of a strategy to make any comparison sorting algorithm stable. How much additional time and space does your strategy entail?
Inversions
Given an array of N Comparable items, design an algorithm to count the number of inversions in the array in O(N log N) runtime. Give a crisp and concise English description of your algorithm.