# Sort an array

Given an array of integers `nums`, sort the array in ascending order.

Example 1:

Input:

``` [5,2,3,1]
```

Output:

``` [1,2,3,5]
```

Example 2:

Input:

```[5,1,1,2,0,0]
```

Output:

```[0,0,1,1,2,5]
```

This problem was taken from Leetcode

## Solution

### The brute force solution.

The brute force solution could be to make two loops and iterate through each elements in the array and repeatedly swapping the adjacent elements if they are in wrong order. This approach is called Bubble sort.

```var nums = [5,4,6,1,2,3];

/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {

for(var i = 0; i < nums.length - 1;i++) {
for(var j=0;j < nums.length - 1; j++) {
if(nums[j] > nums[j+1]) {
var tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
return nums;
}

nums = sortArray(nums);
console.log(nums);```

In the worst case scenario the complexity will be O(n*n) since we have to iterate n*n times where n is the number of elements in the array.

A better performing solution is to keep splitting the array into two halves till we have single elements. Then we start merging the arrays and sorting at the same time. This is called merge sort algorithm.

The diagram is borrowed from Wikipedia.

### Merge sort algorithm implementation:

```/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
function mergeArray(nums, start, mid, end) {
var i = start, j = mid + 1;
var tempArr = [];
// compare till we reach either end of one of the halves
for(var k = start;(i < mid+1 && j < end+1); k++) {
if(nums[i] <= nums[j]) {
tempArr.push(nums[i]);
i++;
}
else {
tempArr.push(nums[j]);
j ++;
}
}

// add the rest from the first half
for(var k = j;k < end + 1; k++) {
tempArr.push(nums[k]);
}
// add the rest from the second half
for(var k = i;k < mid + 1; k++) {
tempArr.push(nums[k]);
}

// set up nums with sorted values
for(var k = start;k < end+1; k++) {
nums[k] = tempArr[k - start];
}
}

function mergeSort(nums, start, end) {
var mid = Math.floor((start + end) / 2);
if(start < end) {
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
mergeArray(nums, start, mid, end);
}
}
mergeSort(nums, 0, nums.length - 1);
return nums;
}
var nums = [5,4,6,1,2,3];
var result = sortArray(nums);
console.log(result);
```

What we just did?
– started to split the array by half (line 39,40) which recursively calls `mergeSort` and keep splitting on smaller and smaller pieces till the array has only 1 element (line 37)

`mergeSort`call sequence:

 Caller Start End Initial Call 0 5 L 0 2 L 0 1 L 0 0 R 1 1 R 2 2 R 3 5 L 3 4 L 3 3 R 4 4 R 5 5