Advanced Techniques with Sorting Algorithms: K-th Largest Element and Inversion Count

Ready for an adventure in sorting algorithms? We will solve two fun problems: "Find the K-th Ordinal Number in a List" and "Count the Number of Flips in a List". These tasks portray situations where we need clever system design. Let's employ Quick Sort and Merge Sort to find efficient solutions. Buckle up!

Picture an array of numbers and a number k. Your mission is to discover the k-th smallest number in that array. k starts from 1, so when k = 1, we seek the smallest number; when k = 2, we want the second smallest, and onwards.

The first solution might involve scanning and shrinking the array by removing the smallest number until you reach the k-th smallest. But this method, while straightforward, has a time complexity of $O(n^2)$ due to continuous array rewriting.

An efficient plan might be to sort the array and then directly select the k-th number:

inputArray.sort((a, b) => a - b);
return inputArray[k - 1];

This method has a better time complexity - $O(n \log n)$. But can we do even better? Quick Sort thinks so.

Quick Sort can provide an optimal solution. We’ll divide the array into two parts using a pivot: the left side contains numbers less than the pivot, while the right side has all greater numbers.

If the pivot's position equals k, that's our answer! If not, we repeat the process on the necessary partition.

It's coding time! Let’s make a function for partitioning in JavaScript.

function partition(arr, low, high) {
  let pivot = arr[low];
  let i = low;

  for (let j = low + 1; j <= high; j++) {
    if(arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i], arr[low]] = [arr[low], arr[i]];
  return i;
}