Now I have finished the algorithm. I can prove the average time complexity is O(nlogn). And the worst time is also O(nlogn) in real-time test but I haven't prove it.
But for my poor English, I cannot translate my Chinese proof into English. I have just added a simple analysis in the code.
Code:
// #############################################################################
// # FileName: A-Bookmark.cpp
// # Author: Zhang Li, Class CS0901
// Huazhong University of Science & Technology
// #############################################################################
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
// # sorting algorithm begin
// #############################################################################
template<typename DataType> class BookmarkSorter
{
public:
static void sort(vector<DataType>& elements)
{
//
// elementList is the linked list
// bookmarks is an array whose elements are pointers to nodes of the linked list
// the data structure costs O(n) space complexity
//
// we will first perform a binary search on bookmarks, find the position for insertion (costs O(nlogn))
// the total time cost of this part is O(nlogn)
//
// then we will insert the data into the linked list (costs O(1))
// the total time cost of this part is (n * O(1)) == O(n)
//
// when we have inserted a certern amount of data into the linked list,
// the bookmark can no longer represent the linked list,
// and the time complexity of inserting a data will increase to O(n)
//
// so it is time to "update" the bookmark. It is very easy because we just simply save the pointers to
// each node of the linked list.
// this happens when this size of linked list is doubled (when we have inserted 1, 2, 4, 8... elements)
// the total time cost of this part is (1 + 2 + 4 + ... + n) == O(n)
//
// the total time complexity of this algorithm is O(nlogn)
//
list<DataType> elementList;
vector<typename list<DataType>::iterator> bookmarks;
typename list<DataType>::iterator scanIterator, insIterator;
if(elements.size() > 1)
{
// we insert the minimum and maximum data first to reduce the problem in binary searching
swap(*min_element(elements.begin(), elements.end()), elements.at(0));
swap(*max_element(elements.begin(), elements.end()), elements.at(1));
elementList.push_back(elements.at(0));
elementList.push_back(elements.at(1));
// insert other data
for(int scanPos = 2; scanPos < elements.size(); scanPos++)
{
// check whether the bookmark needs to update
if(scanPos >= bookmarks.size() * 2)
{
bookmarks.clear();
for(scanIterator = elementList.begin(); scanIterator != elementList.end(); scanIterator++)
bookmarks.push_back(scanIterator);
}
// perform a binary search to find the insert position
int balanceNum = 0, middle, left = 0, right = bookmarks.size() - 1;
while(left <= right)
{
middle = (left + right) / 2;
elements.at(scanPos) < *bookmarks.at(middle) ? right = middle - 1 : left = middle + 1;
}
insIterator = bookmarks.at(right);
// take a linear search to find the real insert position in the list, costs only O(1)
while(elements.at(scanPos) > *insIterator)
{
insIterator++;
// I added the following two lines to auto-balance the bookmark
// so the worst time complexity is expected to be O(nlogn), but I cannot prove it
if(bookmarks.at(right) != elementList.begin() && !(balanceNum++) & 1 == 1)
bookmarks.at(right)++;
}
// now insert data
elementList.insert(insIterator, elements.at(scanPos));
}
elements = vector<DataType>(elementList.begin(), elementList.end());
}
return;
}
};
// #############################################################################
// # sorting algorithm end