<|im_start|>system
You are a senior software engineer and a brilliant problem solver. Write clean, efficient, well-documented, and runnable code solutions for complex problems. Explain your approach, consider edge cases, and provide code in the requested language (defaulting to Python if unspecified).<|im_end|>
<|im_start|>user
Write pseudocode to implement a sorting algorithm using recursion.
<|im_end|>
<|im_start|>assistant
Function sort(array, leftIndex, rightIndex):
  // If leftIndex is greater than or equal to rightIndex, do nothing. 
  If (leftIndex >= rightIndex) : 
      return 
  
  // Get the middle index
  middleIndex = (rightIndex + leftIndex) / 2
  
  // Sort the left side  
  sort(array, leftIndex, middleIndex) 
  
  // Sort the right side 
  sort(array, middleIndex+1, rightIndex) 
  
  // Merge the sides
  merge (array, leftIndex, middleIndex, rightIndex)
  
Function merge(array, leftIndex, middleIndex, rightIndex):
  // Create two temporary arrays;
  leftArray = [middleIndex - leftIndex + 1] 
  rightArray = [rightIndex - middleIndex]
  
  // Copy data from array to the respective arrays  
  for (i = 0 to middleIndex - leftIndex) : 
      leftArray[i] = array[leftIndex + i] 
  for (j = 0 to rightIndex-middleIndex: j++) 
      rightArray[j] = array[middleIndex + 1 + j] 
  
  // sort the leftArray 
  sortLeftArray(leftArray) 
  
  // sort the rightArray 
  sortRightArray(rightArray) 
  
  // merge the sorted halves 
  i = 0     
  j = 0    
  k = leftIndex     
  while (i < sizeof(leftArray) //&& j < sizeof(rightArray)) 
  { 
      if (leftArray[i] <= rightArray[j]) 
      { 
          array[k] = leftArray[i]; 
          i++; 
      } 
      else
      { 
          array[k] = rightArray[j]; 
          j++; 
      } 
      k++; 
  } 
  
  // Copy the remaining elements  
  while (i < sizeof(leftArray)) : 
  { 
      array[k] = leftArray[i]; 
      i++; 
      k++; 
  } 
  
  while (j < sizeof(rightArray)) 
  { 
      array[k] = rightArray[j]; 
      j++; 
      k++; 
  }<|im_end|>
