title: Implementing merge sort by using only one auxiliary array (instead of creating new array recursively)
body: <p>The basic way of implementing merge sort that is available everywhere is one in which we recursively create new left and right array for each time we perform the split - </p>
  
  <p><a href="https://www.geeksforgeeks.org/merge-sort/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/merge-sort/</a>  --> [1]</p>
  
  <p>I want to create only one auxiliary array like it is done in the below link- </p>
  
  <p><a href="https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort" rel="nofollow noreferrer">https://www.coursera.org/learn/algorithms-part1/lecture/ARWDq/mergesort</a> ->[2]  - Minute (7 - 10)</p>
  
  <p><strong>The instructor clearly states that at 9:30 in the video - 
   it's important to not create the auxiliary array in the recursive routine because that could lead to extensive cost of extra array creation. And you'll sometimes see Mergesort performing poorly because of that bug.</strong> </p>
  
  <p>It does not create new arrays recursively. </p>
  
  <p>Basically, I want to write the code mentioned in the coursera link in python</p>
  
  <p>Here is what I have written so far -></p>
  
  <pre class="lang-py prettyprint-override"><code>class merge_sort:
  
      def __init__(self, data):
          self.data = data
  
      aux_array = []
  
  
      def merge(array, aux_array, low, mid, high):
  
          for k in range(low, high):
              aux_array[k] = self.data[k]
  
          i = low
          j = mid + 1
          for k in range(low, high):
              if(i &gt; mid):
                  self.data[k] = aux_array[i]
                  i = i +1
              elif(j &gt; high):
                  self.data[k] = aux_array[j]
                  j = j +1
              elif(aux_array[i] &lt; aux_array[j]):
                  self.data[k] = aux_array[i]
                  i = i +1
              else:
                  self.data[k] = aux_array[j]
                  j = j +1
  
  
      def mergesort(self, data, low, high):
          #high = len(data)
          mid = (high - low)//2
          mergesort(data, low, mid)
          mergesort(data, mid+1, high)
          merge(data, aux_array, low, mid, high)
  
  
      def start_sort(self):
          high = len(self.data) - 1
          self.mergesort(self.data, 0, high)
  
  
  arr = [10,2,30,0,4]
  
  arr1 = merge_sort(arr)
  arr1.start_sort()
  print(arr1)
  </code></pre>
  
  <p>I am currently getting following error - </p>
  
  <pre><code>TypeError: mergesort() takes 3 positional arguments but 4 were given
  </code></pre>
  
  <p>I have tried doing this as well - </p>
  
  <pre class="lang-py prettyprint-override"><code>@classmethod
      def mergesort(cls, data, low, high):
          #high = len(data)
          mid = (high - low)//2
          mergesort(data, low, mid)
          mergesort(data, mid+1, high)
          merge(data, aux_array, low, mid, high)
  
      def start_sort(self):
          high = len(self.data) - 1
          self.mergesort(self.data, 0, high)
  </code></pre>
  
  <p>In this case, I get following error - </p>
  
  <pre><code>NameError: name 'mergesort' is not defined
  </code></pre>