title: How to make sorting with rank stable?
body: <p>The items in sorted list change relative order depending if there are other items in the list. Sorting algorithm is similar to how financial scanner sort companies.</p>
  
  <p>There's the <strong>table of companies with properties</strong> how good is the brand, how chap, risky and profitable it is, and so on.</p>
  
  <pre><code>|symbol|risk|brand|quality|cheapness|profit|
  |------|----|-----|-------|---------|------|
  |BHP   |0   |1    |1      |0.11     |0.1   |
  |MAIL  |1   |1    |-1     |0.06     |0.18  |
  </code></pre>
  
  <p>We want to <strong>sort</strong> the table so that the <strong>best companies to invest into would be at the top</strong>. </p>
  
  <p>To do so we need to compare companies using some weighted combination of its parameters. But there's the problem - the parameters have very different range some are in <code>[0.01..0.3]</code> others are in <code>[1..10]</code>. </p>
  
  <p>To normalise the ranges we going to use <strong>rank sorting</strong>. Sort each column separately and enumerate its values from <code>1 to N</code>. So the table will be turned into the:</p>
  
  <pre><code>|symbol|risk|brand|quality|cheapness|profit|
  |------|----|-----|-------|---------|------|
  |BHP   |1   |1    |2      |2        |1     |
  |MAIL  |2   |1    |1      |1        |2     |
  </code></pre>
  
  <p>Now values are in the same range and we can compare it using weighted combination, below in table are list of weighs to multiply it with company properties and <strong>calculate the score</strong> - single number, for each company:</p>
  
  <pre><code>weights =
         |risk|brand|quality|cheapness|profit|
         |-1  |1    |1      |1        |1     |
  </code></pre>
  
  <p>After <strong>multiplying properties by its weights and summing it up we can calculate the score</strong> for each company. And then <strong>sort the table by the score column</strong> so that companies with the largest scores will be at the top (see the last column):</p>
  
  <pre><code>|symbol|risk|brand|quality|cheapness|profit|score|
  |------|----|-----|-------|---------|------|-----|
  |BHP   |1   |1    |2      |2        |1     |5    |
  |MAIL  |2   |1    |1      |1        |2     |3    |
  </code></pre>
  
  <p>So far it works great and we can see that <strong>BHP is a better company than MAIL</strong>.</p>
  
  <h1>THE PROBLEM</h1>
  
  <p>Let's add more companies:</p>
  
  <pre><code>|symbol|risk|brand|quality|cheapness|profit|score|
  |------|----|-----|-------|---------|------|-----|
  |MAIL  |1   |1    |-1     |0.06     |0.18  |9    |
  |MAR   |0   |1    |1      |0.03     |0.17  |9    |
  |BHP   |0   |1    |1      |0.11     |0.1   |8    |
  |IHG   |0   |1    |1      |0        |0.15  |6    |
  |TRI   |0   |1    |1      |0.02     |0.11  |6    |
  </code></pre>
  
  <p>What's going on? The <strong>order of BHP and MAIL has been changed on the opposite</strong>! That's feels wrong. Our investment decision will be dependent on how many companies we add to the list, doesn't feel like a reliable way to make money.</p>
  
  <p>UPDATE, following the advice I calculated the ranks for the second table. Seems like indeed the algorithm is unstable and is very susceptible to the presence of other items, small difference in the original values can be turned into very large difference in its ranks. As we can see now the difference in profit <code>5/1 = 5</code> versus <code>2/1 = 2</code> when there's only 2 items in the table.</p>
  
  <pre><code>|symbol|risk|brand|quality|cheapness|profit|score|
  |------|----|-----|-------|---------|------|-----|
  |MAIL  |2   |1    |1      |4        |5     |9    | &lt;= profit = 5
  |MAR   |1   |1    |2      |3        |4     |9    | 
  |BHP   |1   |1    |2      |5        |1     |8    | &lt;= profit = 1
  |IHG   |1   |1    |2      |1        |3     |6    | 
  |TRI   |1   |1    |2      |2        |2     |6    |
  </code></pre>
  
  <h1>QUESTION:</h1>
  
  <p>It seems like there's the rank sorting algorithm is not stable and susceptible to the presence of other items in the table, potentially giving very different sorting results. </p>
  
  <p><strong>Is there a way to make it stable?</strong> So the relative order of A and B will be always the same no depending on other items in the list.</p>
  
  <p>What would be <strong>a better option</strong> to sort that list? Column normalisation and use weighted sum of normalised values to calculate the score? (I discarded it because I believed I found holy grail - ranked sorting - and now can just ignore the normalisation).</p>
  
  <h1>CODE</h1>
  
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>const companies2 = [
    { symbol: 'MAIL', risk: 1, brand: 1, quality: -1, cheapness: 0.06,   profit: 0.18 },
    { symbol: 'BHP',  risk: 0, brand: 1, quality: 1,  cheapness: 0.11,   profit: 0.1  }
  ]
  
  const companies5 = [
    { symbol: 'MAIL', risk: 1, brand: 1, quality: -1, cheapness: 0.06,   profit: 0.18 },
    { symbol: 'MAR',  risk: 0, brand: 1, quality: 1,  cheapness: 0.03,   profit: 0.17 },
    { symbol: 'BHP',  risk: 0, brand: 1, quality: 1,  cheapness: 0.11,   profit: 0.1  },
    { symbol: 'IHG',  risk: 0, brand: 1, quality: 1,  cheapness: 0,      profit: 0.15 },
    { symbol: 'TRI',  risk: 0, brand: 1, quality: 1,  cheapness: 0.02,   profit: 0.11 },
  ]
  
  const weights = { risk: -1, brand: 1, quality: 1, cheapness: 1, profit: 1 }
  
  console.log("BHP better than MAIL: \n")
  console.log(sort_with_rank(companies2, weights).map(({ symbol }) =&gt; symbol))
  console.log("\n\n")
  
  console.log("MAIL better than BHP:\n")
  console.log(sort_with_rank(companies5, weights).map(({ symbol }) =&gt; symbol))
  
  
  // Helper functions ----------------------------------------------------------------------
  
  
  function sort_with_rank(table, weights) {
    // Adding ranks
    let containers = table.map((row) =&gt; ({ row, ranks: {} }))
    let sort_key
    for (sort_key in weights) {
      containers = map_with_rank(
        containers,
        ({ row }) =&gt; row[sort_key],
        (item, rank) =&gt; {
          item.ranks[sort_key] = rank
          return item
        }
      )
    }
  
    // Calculating score
    const containers_with_score = containers.map(({ row, ranks }) =&gt; {
      let sort_key, score = 0
      for (sort_key in weights) score += weights[sort_key] * ranks[sort_key]
      return { row, ranks, score }
    })
  
    // Sorting by score
    const sorted = sort_by(containers_with_score, ({ score }) =&gt; -score)
  
    // Mapping to original
    return sorted.map(({ row, score }) =&gt; ({ ...row, score }))
  }
  
  function map_with_rank(list, order_by, map) {
    // Sorting accourding to rank
    const list_with_index = list.map((v, i) =&gt; ({ v, original_i: i, order_by: order_by(v) }))
    const sorted = sort_by(list_with_index, ({ order_by }) =&gt; order_by)
  
    // Adding rank, if values returned by `order_by` are the same, the rank also the same
    const sorted_with_rank = []
    let rank = 1
    for (let i = 0; i &lt; sorted.length; i++) {
      const current = sorted[i]
      if (i &gt; 0 &amp;&amp; current.order_by != sorted[i - 1].order_by) rank++
      sorted_with_rank.push({ ...current, rank })
    }
  
    // Restoring original order and mapping
    const original_with_rank = sort_by(sorted_with_rank, ({ original_i }) =&gt; original_i)
    return original_with_rank.map(({ v, rank }) =&gt; map(v, rank))
  }
  
  function sort_by(list, by) {
    list = [...list]
    list.sort(function(a, b) { return by(a) - by(b) })
    return list
  }</code></pre>
  </div>
  </div>
  </p>