Implementing MergeSort on an array of two-element arrays in JavaScript

Question

I'm trying to use merge sort to sort an array of edge sets, which themselves are represented as 2-element arrays, i.e. the edge EC is ['E', 'C'].

The array I'm trying to sort is [['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'], ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']]. And I want it to sort by the 'from' edge first, and then if two edges have the same 'from' edge, by the 'to' (second) edge.

When I run the following in Firebug, it looks like it's working (from the things I'm printing to the console), but then at the end it gives ['AC', 'AC', 'AC', 'AC', 'AC', ...].

Array.prototype.toString = function(){
  var s = "[";
  if(this.length > 0){
    s += this[0].toString();
    for(var i = 1; i < this.length; i++){
      s += ", " + this[i].toString();
    }
  }
  s += "]";
  return s;
}

var edges = [['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'],
             ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']];

function sortEdges(edges){
  // mergesort
  // split up
  if(edges.length < 2){
    return edges;
  } else {
    var fH = edges.slice(0, Math.floor(edges.length / 2)); // fH: firstHalf
    var sH = edges.slice(Math.floor(edges.length / 2), edges.length); // sH: firstHalf

    console.log(fH.toString());
    console.log(sH.toString());

    fH = sortEdges(fH);
    sH = sortEdges(sH);

    // merge
    var fHC = 0; // fHC: firstHalfCounter
    var sHC = 0; // sHC: secondHalfCounter

    var bothHalves = new Array();
    for(var i = 0; i < edges.length; i++){
      console.log("fHC: " + fHC + ", sHC: " + sHC + ", bothHalves: " + bothHalves.toString());
      if(fHC < fH.length && (sHC >= sH.length || fH[fHC][0] < sH[sHC][0])){ 
        // compare 'from' vertex
        bothHalves.push(fH[fHC]);
        fHC++;
      } else if(fHC < fH.length && fH[fHC][0] == sH[sHC][0]){ 
        // if tied, compare 'to' vertex
        if(fH[fHC][1] <= sH[sHC][1]){
          bothHalves.push(fH[fHC]);
          fHC++;
        } else {
          bothHalves.push(sH[sHC]);
          sHC;
        }
      } else {
        bothHalves.push(sH[sHC]);
        sHC++;
      }
    }
    return bothHalves;
  }
}
edges = sortEdges(edges);
console.log(edges.toString());

Presumably you know that JavaScript has a built-in sort function that would be much much easier to use? — Stephen Thomas
– Stephen Thomas, Commented Jan 18, 2014 at 22:34
Does it sort arrays of arrays though? If so, then yeah, I probably should've just used that. At least this was educational. — Chris Middleton
– Chris Middleton, Commented Jan 18, 2014 at 22:36
Yes. Arrays have a built-in sort function. No need to write your own. — Stephen Thomas
– Stephen Thomas, Commented Jan 18, 2014 at 22:54
I'd have to write my own comparison function to handle this two-element alphabetic sorting though, which might end up being more complicated than just writing the sort from scratch. Thanks for the link though. — Chris Middleton
– Chris Middleton, Commented Jan 19, 2014 at 1:32

DutGRIFF · Accepted Answer · 2014-01-18 22:32:35Z

1

You left out an increment:

Array.prototype.toString = function(){
  var s = "[";
  if(this.length > 0){
    s += this[0].toString();
    for(var i = 1; i < this.length; i++){
      s += ", " + this[i].toString();
    }
  }
  s += "]";
  return s;
}

var edges = [['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'],
             ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']];

function sortEdges(edges){
  // mergesort
  // split up
  if(edges.length < 2){
    return edges;
  } else {
    var fH = edges.slice(0, Math.floor(edges.length / 2)); // fH: firstHalf
    var sH = edges.slice(Math.floor(edges.length / 2), edges.length); // sH: firstHalf

    console.log(fH.toString());
    console.log(sH.toString());

    fH = sortEdges(fH);
    sH = sortEdges(sH);

    // merge
    var fHC = 0; // fHC: firstHalfCounter
    var sHC = 0; // sHC: secondHalfCounter

    var bothHalves = new Array();
    for(var i = 0; i < edges.length; i++){
      console.log("fHC: " + fHC + ", sHC: " + sHC + ", bothHalves: " + bothHalves.toString());
      if(fHC < fH.length && (sHC >= sH.length || fH[fHC][0] < sH[sHC][0])){ 
        // compare 'from' vertex
        bothHalves.push(fH[fHC]);
        fHC++;
      } else if(fHC < fH.length && fH[fHC][0] == sH[sHC][0]){ 
        // if tied, compare 'to' vertex
        if(fH[fHC][1] <= sH[sHC][1]){
          bothHalves.push(fH[fHC]);
          fHC++;
        } else {
          bothHalves.push(sH[sHC]);
          sHC++;
         //  ^^ You left out this increment   <--------------HERE----------------
        }
      } else {
        bothHalves.push(sH[sHC]);
        sHC++;
      }
    }
    return bothHalves;
  }
}
edges = sortEdges(edges);
console.log(edges.toString());

answered Jan 18, 2014 at 22:32

DutGRIFF

5,2331 gold badge36 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Chris Middleton Over a year ago

Wow, thank you. I can't believe I didn't spot that. You, sir/madam, are a lifesaver.

DutGRIFF Over a year ago

@AmadeusDrZaius It happens. Yesterday I spend 30 minutes just to find that I didn't parseInt when grabbing from a textbox and "11"+9 doesn't equal 20... Ha.

Collectives™ on Stack Overflow

Implementing MergeSort on an array of two-element arrays in JavaScript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related