After a fast search we also want to insert fast. For this purpose, sortseq keeps ready the method insert_at(), which also needs a finger; this finger tells it at which position it shall insert a new container.

A call

seq_item new_it = S.insert_at(finger_it, k, i);

first checks whether the container that finger_it refers to contains the key k. If this is the case, the information is set to i in this container. Otherwise, insert_at() inserts a new key-value pair (k,i) behind or in front of the container (k',i') that finger_it refers to. It is a precondition here that k' be either the largest key smaller than k or the smallest key larger than k. In the first case, (k,i) is put in order behind (k',i'), in the second case in front of this pair. So in either case, the insertion takes place next to (k',i') and an item is returned that refers to the container just inserted.

Though, if it is already known that k is larger than k', that is, the insertion must take place behind (k',i'), a call of

seq_item new_it = S.insert_at(finger_it, k, i, LEDA::after);

is even more efficient. If, in contrast, it is known that k is smaller than k', LEDA::before should be specified as the direction of the insertion.

Every version of the method insert_at() takes only expected time O(1).

Sorted sequences are frequently used for sorting; they are particularly efficient if the input is already presorted for the most part. Let us imagine for an experiment that numbers arrive in the input in the following order:

n-1, n-2, n-3, ..., n-f, 0, 1, 2, 3, ..., n-f-1

Therein, n be a very large integer number, for example 5,000,000, and f be a small integer number, for example 50. We want to sort this input sequence of 5,000,000 elements, which is already presorted for the most part, by successively inserting the elements into a sortseq.

As the first possibility, we use the normal insert(), which starts off from the root for every insertion. The total time for n insertions will be O(n·log n), since every search takes O(log n).^[37]

If we think a little bit about the shape of the sequence, we see that the first f insertions all take place at the beginning of the sortseq, all other n-f (and this being the largest part) exactly in front of the f-th element at the end of the sortseq. So it would be wiser to start with the search from the end of the sortseq by means of finger_locate_from_rear() and then, after a finger has been found pointing to the insertion position, to insert the new element by means of insert_at() there. Here the overall running time will be only O(n·log f) because searching from the end will take only time O(log f). We get the same asymptotic running time if we work with the version of finger_locate() that searches from the beginning and the end of the sequence in parallel.

The stroke of genius is coming now, though: If we look at the sequence even more closely, we notice that every insertion takes place exactly one position in front of or behind the last inserted element! It is therefore even wiser to memorize a finger on the last inserted container and to always start the finger search from there. We then need only time O(1) for searching, and altogether, we get a linear time algorithm: The complete running time is only O(n).

The following program executes these experiments. It first creates a list that consists of the above number sequence. Then it inserts every element of the list into a sortseq by means of the methods discussed above. The times are measured with the help of used_time(). To level out measuring errors, every experiment is executed 10 times.

#include <LEDA/sortseq.h>
#include <LEDA/list.h>
#include <LEDA/misc.h>
#include <iostream>

using leda::sortseq;
using leda::seq_item;
using leda::used_time;
using leda::list;
using std::cout;
using std::endl;


int main()
{
  const int n = 5000000;
  const int f = 50;
  const int NUM_EXP = 10; // number of repeated experiments
  
  cout << "n = " << n << "   f = " << f; 
  cout << "   # repeated experiments = " << NUM_EXP << endl;

  sortseq<int,int> S;
  list<int> L;

  seq_item it;
  float startTime;

  // create list of n integers
  for(int i = 1; i <= f; i++)
    L.append(n-i);
  for(int i = 0; i <= n - f - 1; i++)
    L.append(i);

  int k;
  leda::list_item lit;

  // experiment 1:
  // insert all ints without finger search
  startTime = used_time(); 
  for(int num_exp = 0; num_exp < NUM_EXP; num_exp++) {
    S.clear();
    forall(k, L) 
      S.insert(k, 0);
  }
  cout << "Time to insert without finger search: " 
       << used_time(startTime) << endl;


  // experiment 2:
  // insert all ints with finger search from rear end
  // make sortseq empty for 2nd experiment
  startTime = used_time(); 
  for(int num_exp = 0; num_exp < NUM_EXP; num_exp++) {
    S.clear();
    // insert first element of L into S
    lit = L.first();
    S.insert(L.contents(lit), 0);
    lit = L.succ(lit);
    // insert remaining elements of S into L
    while(lit != nil)
      {
        k = L.contents(lit);
        it = S.finger_locate_from_rear(k); 
        if(it) S.insert_at(it, k, 0, LEDA::before);
        else   S.insert_at(S.max_item(), k, 0, LEDA::after);
        lit = L.succ(lit);
      }
  }
  cout << "Time to insert with finger search from rear: " 
       << used_time(startTime) << endl;

  // experiment 3:
  // insert all ints with finger search from both ends
  startTime = used_time();
  for(int num_exp = 0; num_exp < NUM_EXP; num_exp++) {
    S.clear();
    lit = L.first();
    S.insert(L.contents(lit), 0);
    lit = L.succ(lit);
    while(lit != nil)
      {
        k = L.contents(lit);
        it = S.finger_locate(k);
        if(it) S.insert_at(it, k, 0, LEDA::before);
        else   S.insert_at(S.max_item(), k, 0, LEDA::after);
        lit = L.succ(lit);
      }
  }
  cout << "Time to insert with finger search from both ends: " 
       << used_time(startTime) <<" "<< endl;

  
  // experiment 4:
  // insert all ints with previous finger search
  startTime = used_time(); 
  for(int num_exp = 0; num_exp < NUM_EXP; num_exp++) {
    S.clear();
    lit = L.first();
    it = S.insert(L.contents(lit), 0);
    lit = L.succ(lit);
    while(lit != nil)
      {
        k = L.contents(lit);
        it = S.finger_locate(it, k); // use it here as the finger
        it = ( it ? S.insert_at(it, k, 0, LEDA::before)
               : S.insert_at(S.max_item(), k, 0, LEDA::after)
               );  // again, store it for succeeding finger search
        lit = L.succ(lit);
      }
  }
  cout << "Time to insert with finger search from last insertion: " 
       << used_time(startTime) <<" "<< endl;
  
  cout << endl;
}

The first element in a sortseq must always be inserted by an insert() because no item can be available at this time yet. In the experiments 2, 3, and 4, the first element is inserted intentionally outside the loop in order not to have to make the test whether the sortseq is still empty in every iteration; this would cause additional costs of O(n) and thereby could distort the measurement results.

A test run on one of the machines available to the author produced the following times:

Time to insert without finger search: 26.989
Time to insert with finger search from rear: 23.463
Time to insert with finger search from both ends: 24.846
Time to insert with finger search from last insertion: 15.242

We see by this that it always pays off to use finger search. As expected, the version with parallel finger search from the beginning and the end is slower than the one that searches only from the end. Despite this parallel finger search taking twice the time as before, it is not fundamentally slower because the biggest part of the time is used up for inserting. The version memorizing a finger to the last inserted element and starting the next search from there is considerably faster than all other ones.