Mergesort

This program sorts a list of random numbers. The numbers are stored in a variable with the name "fulllist" which is created by the random number generator:

      function randomlist(list)
        { var k;
          var h = window.prompt("How many Random Numbers should be sorted?");
          for (k=0;k<h;k=k+1)
           { list.push(Math.floor(10+90*Math.random())); } }
      .....
      var fulllist = new Array();
      randomlist(fulllist);

The list contains a h random numbers from 10 to 99 where h is given by the user. The unsorted list is held in fulllist.before previous to the call of the sorting algorithm. The implemented sorting algorithm is the following:

      function mergesort(list)
        { var k;
          k = Math.floor(list.length/2);
          if (k < 1) { return; }
          var left = new Array();
          var right = new Array();
          while (list.length>k) { left.push(list.shift()); }
          while (list.length>0) { right.push(list.shift()); }
          mergesort(left); mergesort(right);
          while ((left.length > 0) && (right.length > 0))
            { count = count+1;
              if (left[0] < right[0])
                { list.push(left.shift()); }
              else
                { list.push(right.shift()); } }
          while (left.length > 0) 
            { list.push(left.shift()); }
          while (right.length > 0)
            { list.push(right.shift()); }
          return; }

It roughly does the following.

When called, the valriable "list" has in the part "before" an unsorted list.

If the length of this list is at least 2, then k is at least one and the list is split into the sublists "left" and "right": as long as there are more than k elements in the list, the first element is moved into the sublist "left", afterwards the remaining k elements are moved into the sublist "right".

Then the two sublists are sorted by a recursive call of "mergesort".

After that, the subroutine merges these two sorted lists into one list. Note that "list" is the empty list when starting the merging process. The merging is done iteratively: As long as both lists "left" and "right" are not empty, the algorithm looks which list starts with a smaller value and "shifts" then this smaller value out of the current list and pushes it to the final position of the combined list in the variable "list". This loops terminates when one of the lists "left" and "right" is empty. Then the next lines move the nonempty one of these lists element by element to the final position of "list". Then "list" is the sorted copy of "list" and the routine is completed.

If the length of the list is less than 2, then k is zero and the list is not modified as it is already sorted.

Java Script starts here.

Java Script ends here.