c++median-of-medians

Median of medians understanding the code


I found an implementation of algorithm in c++ here https://gist.github.com/andlima/1774060 but I don't understand a purpose of few lines and how they work,

  1. Should I add an if statement that if n is below certain amount we should just sort an array and return v[k]?
  2. In 4th line, why we create a variable by increasing it by 4? I understand that we have to divide it by 5 in order to have an amount of little arrays
  3. What is that "for loop" in 6 line responsible for? Is it for spliting main array into smaller ones which we wanna sort and then create an array of medians? Why there is a swap function and why we split it into if and else conditions?
  4. Why we delete medians array after calling same function line before
  5. What is the purpose of for loop in 25 line and this in 33 and also swap in 38?

I'll be really really grateful for any help with this.


Solution

    1. This is an optimization. An implementation can do it, but it does not have to do it.
    2. Adding four is done to round the result of the division by five. This is a common trick with integer division: if you would like to round up the result of dividing by N, add N-1 before the division.
    3. The loop on line 6 is responsible for iterating five-element chunks of the array. The if condition checks if the chunk has five elements. The for loops inside perform a selection sort, swapping elements to place the median at index w[2]
    4. We delete medians as soon as the recursive invocation is over, because the rest of the algorithm does not need it.
    5. Loop on line 25 moves pivot to the end position of the array.