1+ public class Solution {
2+
3+ private int [ ] aux ; // Auxiliary array for merging
4+
5+ /// <summary>
6+ /// Sorts the input array using the classical merge sort algorithm. Uses
7+ /// aux array to save space instead of keeping copies of all array segments
8+ /// </summary>
9+ /// <param name="nums">The input array of integers to be sorted</param>
10+ /// <returns>The sorted array of integers</returns>
11+ public int [ ] SortArray ( int [ ] nums )
12+ {
13+ // Optimization: early return for empty arrays or arrays with one element
14+ if ( nums == null || nums . Length <= 1 ) return nums ;
15+
16+ aux = new int [ nums . Length ] ;
17+ MergeSort ( nums , 0 , nums . Length - 1 ) ;
18+
19+ return nums ;
20+ }
21+
22+ /// <summary>
23+ /// Recursively divides and merges the array segments
24+ /// </summary>
25+ /// <param name="nums">The input array of integers to be sorted</param>
26+ /// <param name="left">The start index of the segment to be sorted</param>
27+ /// <param name="right">The end index of the segment to be sorted</param>
28+ private void MergeSort ( int [ ] nums , int left , int right )
29+ {
30+ // Base case: return when left has crossed right
31+ if ( left >= right ) return ;
32+
33+ // Get new mid to halve the array segment
34+ int mid = ( left + right ) / 2 ;
35+
36+ // Sort the first and the second halves
37+ MergeSort ( nums , left , mid ) ;
38+ MergeSort ( nums , mid + 1 , right ) ;
39+
40+ // Copy to aux[]
41+ for ( int k = left ; k <= right ; k ++ )
42+ {
43+ aux [ k ] = nums [ k ] ;
44+ }
45+
46+ // Merge back to nums[]
47+ // two pointers to help merge
48+ int i = left , j = mid + 1 ;
49+ for ( int k = left ; k <= right ; k ++ )
50+ {
51+ // If current left has crossed mid, nums Kth value should be current jth of aux; j++
52+ // Implies all the left elements have been merged; now we just add the remaining right elements, one by one, in order.
53+ if ( i > mid ) nums [ k ] = aux [ j ++ ] ;
54+ // Else if current j has crossed right, nums kth value should be ith of aux; i++
55+ // Implies all the right elements have been merged; now we just add the remaining left elements, one by one, in order.
56+ else if ( j > right ) nums [ k ] = aux [ i ++ ] ;
57+ // Else if ith value is greater than jth value in aux, nums kth value should be jth of aux; j++
58+ else if ( aux [ i ] > aux [ j ] ) nums [ k ] = aux [ j ++ ] ;
59+ // Else nums[k] is the left most unsorted value; i++
60+ else nums [ k ] = aux [ i ++ ] ;
61+ }
62+ }
63+ }