title: MergeSort in scala
body: <p>I came across another <a href="http://www.codechef.com/problems/INSOMA3" rel="nofollow">codechef problem</a> which I am attempting to solve in Scala. The problem statement is as follows:</p>
  
  <blockquote>
    <p>Stepford Street was a dead end street. The houses on Stepford Street
    were bought by wealthy millionaires. They had them extensively altered
    so that as one progressed along the street, the height of the
    buildings increased rapidly. However, not all millionaires were
    created equal. Some refused to follow this trend and kept their houses
    at their original heights. The resulting progression of heights was
    thus disturbed. A contest to locate the most ordered street was
    announced by the Beverly Hills Municipal Corporation. The criteria for
    the most ordered street was set as follows: If there exists a house
    with a lower height later in the street than the house under
    consideration, then the pair (current house, later house) counts as 1
    point towards the disorderliness index of the street. It is not
    necessary that the later house be adjacent to the current house. Note:
    No two houses on a street will be of the same height For example, for
    the input: 1 2 4 5 3 6 The pairs (4,3), (5,3) form disordered pairs.
    Thus the disorderliness index of this array is 2. As the criteria for
    determining the disorderliness is complex, the BHMC has requested your
    help to automate the process. You need to write an efficient program
    that calculates the disorderliness index of a street.</p>
  </blockquote>
  
  <p>A sample input output provided is as follows:</p>
  
  <blockquote>
    <p>Input: 1 2 4 5 3 6</p>
    
    <p>Output: 2</p>
  </blockquote>
  
  <p>The output is 2 because of two pairs (4,3) and (5,3)</p>
  
  <p>To solve this problem I thought I should use a variant of MergeSort,incrementing by 1 when the left element is greater than the right element.</p>
  
  <p>My scala code is as follows:</p>
  
  <pre><code>    def dysfunctionCalc(input:List[Int]):Int = {
          val leftHalf = input.size/2
          println("HalfSize:"+leftHalf)
  
          val isOdd = input.size%2
          println("Is odd:"+isOdd)
  
          val leftList = input.take(leftHalf+isOdd)
          println("LeftList:"+leftList)
  
          val rightList = input.drop(leftHalf+isOdd)
          println("RightList:"+rightList)
  
          if ((leftList.size &lt;= 1) &amp;&amp; (rightList.size &lt;= 1)){
                  println("Entering input where both lists are &lt;= 1")
                               if(leftList.size == 0 || rightList.size == 0){
                                        println("One of the lists is less than 0")
                                          0
                                  }
                               else if(leftList.head &gt; rightList.head)1 else 0
       }       
       else{
               println("Both lists are greater than 1")
               dysfunctionCalc(leftList) + dysfunctionCalc(rightList)
       }
     }
  </code></pre>
  
  <p>First off, my logic is wrong,it doesn't have a merge stage and I am not sure what would be the best way to percolate the result of the base-case up the stack and compare it with the other values. Also, using recursion to solve this problem may not be the most optimal way to go since for large lists, I maybe blowing up the stack. Also, there might be stylistic issues with my code as well.</p>
  
  <p>I would be great if somebody could point out other flaws and the right way to solve this problem.</p>
  
  <p>Thanks</p>