Merge Sort Example

by hesster92

HTML

List Size:
<input type="textbox" id="size" value="20" />
<br/>

<table>
  <tr>
    <th>
      <input type="button" value="Create Random List" onClick="createList();" />
    </th>
    <th>
      <input type="button" value="Merge Sort" onClick="startMergeSort()" />
    </th>
  </tr>
  <tr>
    <td>
      <p id="rawlist"></p>
    </td>
    <td>
      <p id="mergesortoutput"></p>

    </td>
  </tr>
</table>

<br/>

JavaScript

var DoublyLinkedList = function() {
  this.head = null;
  this.tail = null;
  this.length = 0;

  this.clear = function() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  };

  // Adds Node to the tail of the List
  this.add = function(_content) {
    if (this.head == null) {
      this.head = new LinkedListNode(_content);
      this.length++;
      return this.head;
    }
    if (this.tail == null) {
      this.tail = new LinkedListNode(_content);
      this.head.next = this.tail;
      this.tail.last = this.head;
      this.length++;
      return this.tail;

    }
    this.tail.next = new LinkedListNode(_content);
    this.tail.next.last = this.tail;
    this.tail = this.tail.next;
    this.tail.next = null;
    this.length++;
    return this.tail;

  };

  // Creates a independent copy of the current list
  this.copy = function() {
    var newlist = new DoublyLinkedList();
    var node = this.head;

    while (node != null) {
      newlist.add(node.content);
      node = node.next;
    }
    return newlist;
  }

  // Pulls from the top of the List, removes Node
  this.pop = function() {
    if (this.head == null) {
      this.length = 0;
      return null;
    }
    // Case of one node
    if (this.length == 1) {
      var a = this.head;
      this.tail = null;
      this.head = null;
      this.length = 0;
      return a;
    }

    // Case of length > 1
    var a = this.head; // hold value for return
    this.head = this.head.next;
    this.head.last = null;
    this.length--;
    return a;
  };

  this.toString = function() {
    var str = this.length + ' nodes <br/>';
    var node = this.head;

    while (node != null) {
      str += node.content + "<br/>";
      node = node.next;
    }
    return str;
  };
}

var LinkedListNode = function(_content) {
  this.next = null;
  this.last = null;
  this.content = _content;
}

// This is the list used universally to sort
var list = new DoublyLinkedList();

function createList() {
  var n =...