About quick sorting, complexity 2 * N

A quick sorting algorithm has recently been developed whose complexity is defined as 2 * N (2 times N).

In this article, we will not analyze the sorting algorithm itself, but only after conducting a series of tests, we compare it with the sorting used in Visual Studio (the std :: sort function). As they say: only facts and a minimum of emotions.

We will sort the text information, as which we will consider an array of words. This array will be formed on the basis of literary works. To do this, we put all the words of these works in order in this array. The word breaking occurs without modernization, a sign of the beginning of a new word is a gap. The words in the array fully correspond to the words in the text. Since punctuation marks (periods, commas, and so on) and control characters are written behind words without spaces, as a result, they are part of words. Separate punctuation marks and control characters are treated as separate words. The files contain the addresses of sites where these files are located. Address data is one word. The longest word consists of 95 characters. In the works under consideration there are letters of the Latin alphabet,Cyrillic, punctuation and control characters.

Sorted information is arbitrary, not ordered in any way, and, as a result, special sortings are not applied.

Two sorting methods are compared: the newly developed sorting algorithm with 2 * N complexity and the algorithm used in Visual Studio 2017 (std :: sort function). They are interested in the sorting time and the amount of each method used for this memory on each test.

Programs are written in the environment - Visual Studio 2017, on the platform - Windows x64. Testing was carried out in 2 configurations. The test results in the Debug configuration and Release configuration are presented in tables 1 and 2, respectively. The tables show the results of testing two sorting methods.

Since the results on the calculation time are floating (the values ​​vary within 10%), a series of calculations was carried out for each test, from which the smallest values ​​were selected and these values ​​were put in tables. The times indicated in columns 4 and 6 are only sorting times. Additional processes (such as reading and writing to a file, array formation) are not included in the specified time.

Time efficiency$$$E_t$ and from memory$$$E_m$ calculated according to the following formulas, respectively:

$$

$$E_t =100\frac{T_1 - T_2}{T_1}, \qquad \qquad \qquad E_m =100\frac{M_1 - M_2}{M_1},$$

Where $$$T_1, T_2$- the number of time steps for which the std :: sort function used in Visual Studio is executed, and the new sorting algorithm, respectively;$$$M_1, M_2$ - the amount of memory used to execute the std :: sort function used in Visual Studio, and the new sorting algorithm, respectively.

Table 1.


Table 2.


How much the newly developed sorting algorithm with complexity 2 * N is more efficient (both in time and in memory usage) of the algorithm used in Visual Studio 2017 (function std :: sort) is up to you to decide.