Insertion Sort Example

by Ron Eaglin

HTML

List Size:
<input type="textbox" id="size" value="20" />
<br/>
Insertion Value:
<input type="textbox" id="insert" value="abc" />
<input type="button" value="Insert" onClick="insertValue();" />
<br/>

<table>
  <tr>
    <th>
      <input type="button" value="Create Random List" onClick="createList();" />
    </th>
    <th>
      <input type="button" value="Merge Sort" onClick="startMergeSort()" />
    </th>
    <th>
      <input type="button" value="Insertion Sort" onClick="startInsertionSort()" />
    </th>

</tr>
  <tr>
    <td>
      <p id="rawlist"></p>
    </td>
    <td>
      <p id="mergesortoutput"></p>

    </td>
    <td>
      <p id="insertsortoutput"></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;
  }
  
  // Push adds to the head of the List (like a Stack)
  this.push = function(_content) {
     var node = new LinkedListNode(_content);
     node.next = this.head;
     this.head.last = node;
     this.head = node;
     length++;
     return node;
  }

  this.addSorted = function(_content) {
     if (this.head == null) {return this.add(_content); }
     
     // Push onto top of node if it should be first element
     if (_content < this.head.content) {return this.push(_content);}
     
     // Go through each node and insert at sorted location
     var node = this.head;
     while (node.next != null) {
       if ((_content > node.content) && (_content <= node.next.content)) {
           var newNode = new LinkedListNode(_content);
           newNode.next = node.next;
           newNode.last = node;
           node.next = newNode;
           this.length++;
           return newNode;
       }
       node = node.next;
     }
     
     // If at last node - simply add to tail
     return this.add(_content);
  }

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

    while (node != null) {
     ...