[tabby title=”Task”]

 [5,2,3,1]

 [1,2,3,5]

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

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

This problem was taken from Leetcode

[tabby title=”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)

mergeSortcall sequence:

[tabbyending]