Sort and Merge Array

Question

I have to merge two arrays and sort by created value based on comparison. I don't want to use any inbuilt js functions like sort. I tried using while loop but couldn't figure out exact solution. Here is my sample code:

function merge(a, b, n, m)  
{  
    res = []; 
    i = 0; j = 0; k = 0;  
    while(i < n && j < m) {
        if(a[i]['created'] < b[j]['created']) {
            res.push(a[i]);
            i++;
        } else {
            res.push(b[j]);
            j++;
        }        
    }

    while(i < n) {
        res.push(a[i]);
        i++;
    }

    while(j < m) {
        res.push(b[j]);
        j++;
    }
    return res;  
}  

a = [{'title':'title1', 'created':'18'},{'title':'title2', 'created':'16'},{'title':'title3', 'created':'20'}];  
b = [{'title':'title4','created':'17'},{'title':'title5','created':'19'}];  
n = a.length;  
m = b.length;  

var endResult = merge(a, b, n, m);  
console.log(endResult);

My expected Output should be as follows:

[{'title':'title2', 'created':'16'},{'title':'title4','created':'17'},{'title':'title1', 'created':'18'},{'title':'title5','created':'19'},{'title':'title3', 'created':'20'}];

Please let me know what i missed out here.

Note: I don't want to use in-built Javascript function like sort(). I have to sort values based on specific business logic, which i shall implement after figuring out basic sort.

Is this some kind of interview "stump you with algs" question? Why wouldn't you use the functions any professional would use to do this? — Tim Consolazio
– Tim Consolazio, Commented Jan 23, 2019 at 21:17
@TimConsolazio My end result is not just a sorted array. I have to implement many other conditions for sorting. Just i am stuck up with basic sorting part. — Ganesh Babu
– Ganesh Babu, Commented Jan 23, 2019 at 21:19
The first issue I can note is that you are only comparing elements of array a with elements of array b. You need to compare elements that belong to the same array too. — Shidersz
– Shidersz, Commented Jan 23, 2019 at 21:19
Writing a sort routine is straightforward. There are plenty of examples of BubbleSorts, QuickSorts, TimSorts, MergeSorts, and others online. While you could easily write your own version of one of these, it would very likely offer nothing over writing your code with a custom comparator supplied to the built-in sort. You can even reuse that comparator in a merge step. A custom sort only makes sense if you're doing it as a learning exercise. — Scott Sauyet
– Scott Sauyet, Commented Jan 23, 2019 at 21:28

RaminS · Accepted Answer · 2019-01-23 21:36:08Z

A simple O(n^2) solution would be to loop through all elements looking for the lowest value, then looping through them all again looking for the second lowest value, etc.

function mergeSort(a, b) {
    var array = a.concat(b);
    var length = array.length;
    var results = [];
    while(results.length < length) {
	var currentLowest = 0;
	for(var i = 1; i < array.length; i++) {
	    if(array[i].created < array[currentLowest].created) {
		currentLowest = i;
	    }
	}
	results.push(array[currentLowest]);
	array.splice(currentLowest,1);
    }
    return results;
}

a = [{'title':'title1', 'created':'18'},{'title':'title2', 'created':'16'},{'title':'title3', 'created':'20'}];  
b = [{'title':'title4','created':'17'},{'title':'title5','created':'19'}];

var endResult = mergeSort(a,b);
document.getElementsByTagName('p')[0].innerHTML = JSON.stringify(endResult);

<p></p>

Nina Scholz · Accepted Answer · 2019-01-23 21:29:37Z

1

You could take a nested loop and sort the array after concat.

function sort(array) {
    var sorted = [],
        i = array.length,
        j;

    while (i--) {
        for (j = 0; j < sorted.length; j++) {
            if (array[i].created < sorted[j].created) {
                break;
            }
        }
        sorted.splice(j, 0, array[i]);
    }
    return sorted;
}

var a = [{ title: 'title1', created: '18' }, { title: 'title2', created: '16' }, { title: 'title3', created: '20' }],
    b = [{ title: 'title4', created: '17' }, { title: 'title5', created: '19'}],
    result = sort(a.concat(b));

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered Jan 23, 2019 at 21:29

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Comments

Cat · Accepted Answer · 2019-01-23 22:57:29Z

This seems to work well, although I can't speak to its speed.

  const arr1 = [111,2,300,50,6,71,9];
  const arr2 = [122,8,40,29,611,74,1];
  // Combines the two arrays into one
  const unsorted = arr1.concat(arr2);
  const sorted = [];

  for(i = 0; i < unsorted.length; i++){
    // Adds all elements from the unsorted array to the destination (sorted) array
    insert(unsorted[i], sorted);
  }
  console.log(sorted);

  function insert(item, arr){
    // Adds the first item automatically
    if(arr.length == 0){
      arr.push(item); 
      return; 
    }
    for(let i = 0; i < arr.length; i++){
      if(i + 1 == arr.length){
        // Adds the item at the end of the array because it's so big 
        arr.push(item);
        break;
      }

      else if(item < arr[i]){
        // Adds the item at the appropriate position in the sorted array
        arr.splice(i, 0, item);
        break;
      }
    }
  }

Scott Sauyet · Accepted Answer · 2019-01-24 00:09:01Z

This is very easy to do with the built-in sort and concat functions.

Custom logic can be supplied to the comparator function. It's hard to imagine any required sorting that can't be done this way.

// `comparator` contains your custom business logic.  Return a negative number if `a`
// is smaller than `b`, a positive one if it's larger, and 0 if they're equal.

const mergeAndSort = (comparator) => (a, b) => a.concat(b).sort(comparator)

const myComparator = (a, b) => {
  return Number(a.created) - Number(b.created)  // or just `a.created - `b.created`
}

const a = [{ title: 'title1', created: '18' }, { title: 'title2', created: '16' }, { title: 'title3', created: '20' }],
      b = [{ title: 'title4', created: '17' }, { title: 'title5', created: '19'}]

console.log(mergeAndSort(myComparator)(a, b))

Is this an attempt to learn how to write a sort algorithm? If not, then I would go with an approach like this.

Collectives™ on Stack Overflow

Sort and Merge Array

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related