What sort algorithm is this?

[Alex Sokolek]

Hi. Does anyone recognize this sort algorithm?

BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
if (compare(_NodeList[i + 0]->Item, _NodeList[i + j]->Item) > 0)
{
swap = true;
TempNode = _NodeList[i+0];
_NodeList[i+0] = _NodeList[i + j];
_NodeList[i + j] = TempNode;
}
}
}
}


It is similar to a bubble-sort, except that it has an outer loop that runs the interval (j) from half the list, then a quarter of the list, then an eigth of the list, and so on until it is at an interval of 1. I get a factor of ten improvement in performance over the bubble-sort.

I think this is a merge-exchange-sort, but i'm not certain, so I'm asking for insight. Thanks.

p.s. Does anyone know how to include code and keep the indents. I tried tab and spaces - it did not work.

 

[ChatGPT]

Hello,
Your observation is close, but this algorithm is actually the Shellsort algorithm, not a merge-exchange sort. Yes, it is somewhat similar to bubble sort but with some significant improvements.
Shellsort, also known as Shell sort or Shell's method, was invented by Donald Shell in 1959. It is an in-place comparison sort that begins by sorting pairs of elements far apart from each other and progressively reduces the gap between elements being compared. By starting with far apart elements, it can quickly move some out-of-place elements into the right position faster than a simple nearest neighbor exchange.
The algorithm you posted adopts the simple version of Shellsort with a gap sequence [N/2, N/4, N/8, ..., 1]. It uses comparison to compare elements gap distance apart and swaps them if they are in the wrong order, repeating this process until the list is sorted.
Shellsort's performance highly depends on the gap sequence you choose. The 'half-half' sequence you posted is the original sequence used by Shell (worst-case time complexity O(N^2)), but some more complex sequences yield better time complexity (for example, the best known is O(N log^2 N)).
Therefore, you see a significant improvement over simple bubble sort, which has a worst-case and average time complexity of O(N^2) due to the fact that it only swaps adjacent items when they are out of order. Shell's method with the decrease by half sequence improves this by swapping items that are far apart, and then progressively reducing the gap, thus "compacting" the list quicker.

 

[Alex Sokolek]

Hi. Does anyone recognize this sort algorithm. I think it is called a merge exchange sort, but I'm not certain. I learned it many years ago, and I get a factor of ten improvement over the bubble sort. Thank you.

BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
if (compare(_NodeList[i + 0]->Item, _NodeList[i + j]->Item) > 0)
{
swap = true;
TempNode = _NodeList[i + 0];
_NodeList[i + 0] = _NodeList[i + j];
_NodeList[i + j] = TempNode;
}
}
}
}

 

[Alex Sokolek]

This is a test. I am testing my ability to provide code examples and retain white-space.

```c++
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
```

 

[Alex Sokolek]

This is also a test.

~~~C++
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
~~~

 

[Alex Sokolek]

This is a third test.

\```
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
\```