Sorting speed comparation (bubble, insertion, quick, radix, counting, combined, STL)

sort_time_compare.cpp

// Sorting comparation (bubble, insertion, quick, radix, counting, combined, STL)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <random>
#include <chrono>
#include <functional>

using std::cout;
using std::vector;

#define ARRAY_SIGNED_VALUES                 // use signed type
#define ARRAY_SIZE 65536                    // size of test arrays
#define ARRAY_HUGE_SIZE (ARRAY_SIZE * 256)  // size of huge test arrays
#define QUICKINS_SORT_THRESHOLD 16          // threshold to use insertion sort for subarrays with size less than specified value

// Minimum and maximum random number values
#ifdef ARRAY_SIGNED_VALUES
  #define ARRAY_RAND_MIN (-32768)
  #define ARRAY_RAND_MAX 32767
#else
  #define ARRAY_RAND_MIN 0
  #define ARRAY_RAND_MAX 65535
#endif

#define COUNTING_SORT_MAX_RANGE (ARRAY_RAND_MAX - ARRAY_RAND_MIN + 1)  // maximum range of numbers for counting sort

// Type of sorting data
#ifdef ARRAY_SIGNED_VALUES
  using Data = int32_t;
#else
  using Data = uint32_t;
#endif
using DataIter = vector<Data>::iterator;  // vector of Data iterator type

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Bubble sort

void bubble_sort(const DataIter first, DataIter last)
{
  --last;
  for (auto i_it = first; i_it != last; ++i_it) {
    bool swapped = false;
    for (auto j_it = first, last_j = std::next(first, last - i_it); j_it != last_j; ++j_it) {
      if (*j_it > *std::next(j_it)) {
        std::swap(*j_it, *std::next(j_it));
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}

// Combined (insertion and bubble) sort
// SOMETIMES CRASHES -- CONTAINS AN ERROR !!!
void insbubble_sort(const DataIter first, DataIter last)
{
  --last;
  for (auto i_it = first; i_it != last; ++i_it) {
    bool swapped = false;
    auto min_it = i_it;
    for (auto j_it = i_it, last_j = std::next(first, last - i_it); j_it != last_j; ++j_it) {
      if (*j_it > *std::next(j_it)) {
        std::swap(*j_it, *std::next(j_it));
        swapped = true;
      }
      if (*j_it < *min_it) { min_it = j_it; }
    }
    if (!swapped) break;
    if (min_it != i_it) {
      std::swap(*i_it, *min_it);
    }
  }
}

// Straight insertion sort
void insertion_sort(const DataIter first, const DataIter last)
{
  for (auto key_it = std::next(first); key_it != last; ++key_it) {
    Data key = *key_it;
    auto copy_it = key_it;
    for (; copy_it > first && *std::prev(copy_it) > key; --copy_it) {
      *copy_it = *std::prev(copy_it);
    }
    *copy_it = key;
  }
}

// Binary insertion sort
void binins_sort(const DataIter first, const DataIter last)
{
  for (auto key_it = std::next(first); key_it != last; ++key_it) {
    Data key = *key_it;
    DataIter from_it = std::upper_bound(first, key_it, key);
    std::copy_backward(from_it, key_it, std::next(key_it));
    *from_it = key;
  }
}

// Quick sort
void quick_sort(DataIter first, DataIter last)
{
  while (last - first >= 2) {
    if (last - first == 2) {
      if (*first > *std::next(first)) { std::swap(*first, *std::next(first)); }
      return;
    }

    Data pivot = *std::next(first, (last - first) / 2);
    auto left = std::partition(first, last, [pivot](const Data el) { return el < pivot; });
    auto right = std::partition(left, last, [pivot](const Data el) { return !(pivot < el); });

    if (left - first > last - right) {
      if (last - right >= 2) { quick_sort(right, last); }
      last = left;
    } else {
      if (left - first >= 2) { quick_sort(first, left); }
      first = right;
    }
  }
}

// Intermediary function for combined (quick and insertion) sort (see below)
void quick_sort_uncompleted(DataIter first, DataIter last)
{
  while (last - first >= QUICKINS_SORT_THRESHOLD) {
    Data pivot = *std::next(first, (last - first) / 2);
    auto left = std::partition(first, last, [pivot](const Data el) { return el < pivot; });
    auto right = std::partition(left, last, [pivot](const Data el) { return !(pivot < el); });

    if (left - first > last - right) {
      if (last - right >= QUICKINS_SORT_THRESHOLD) { quick_sort_uncompleted(right, last); }
      last = left;
    } else {
      if (left - first >= QUICKINS_SORT_THRESHOLD) { quick_sort_uncompleted(first, left); }
      first = right;
    }
  }
}

// Combined (quick and insertion) sort
void quickins_sort(DataIter first, DataIter last)
{
  quick_sort_uncompleted(first, last);
  insertion_sort(first, last);
}

// Most significant bit number
inline int msb(std::make_unsigned<Data>::type n)
{
  int size = sizeof(Data) * 4, shift = sizeof(Data) * 2;
  std::make_unsigned<Data>::type mask = (1 << sizeof(Data) * 4) - 1;
  int result = 0;

  while (n > 1) {
    Data low = n >> size;
    if (low) {
      n = low;
      result += size;
    } else {
      n &= mask;
    }
    size >>= 1;
    mask >>= shift;
    shift >>= 1;
  }

  return result;
}

// Radix sort (MSD by 1 bit) [implementation for internal use]
void radix_sort_msd1b_impl(DataIter first, DataIter last, const Data mask, std::make_unsigned<Data>::type bit)
{
  while (last - first >= 2) {
    if (last - first == 2) {
      if (*first > *std::next(first)) { std::swap(*first, *std::next(first)); }
      return;
    }
  
    auto middle = std::partition(first, last, [bit](const Data n) { return (n & bit) == 0; });
    do { bit >>= 1; } while(bit && (mask & bit) == 0);
    if (!bit) { return; }

    if (middle - first > last - middle) {
      if (last - middle >= 2) { radix_sort_msd1b_impl(middle, last, mask, bit); }
      last = middle;
    } else {
      if (middle - first >= 2) { radix_sort_msd1b_impl(first, middle, mask, bit); }
      first = middle;
    }
  }
}

// Radix sort (MSD by 1 bit)
void radix_sort_msd1b(const DataIter first, const DataIter last)
{
  // Get mask of bits with different values of numbers in range or zero if range is sorted
  auto get_mask = [](const DataIter first, const DataIter last) {
    Data prev = *first, mask_or = prev, mask_and = prev;
    bool sorted = true;
    for_each(std::next(first), last, [&](const Data n) {
      mask_or |= n;
      mask_and &= n;
      if (n < prev) { sorted = false; }
      prev = n;
    });
    return sorted ? 0 : mask_or ^ mask_and;  // mask_or & ~mask_and;
  };

  Data mask = get_mask(first, last);
  if (mask > 0) {
    radix_sort_msd1b_impl(first, last, mask, 1 << msb(mask));
    return;
  }
  if (std::is_signed<Data>::value && (mask < 0)) {
    auto middle = std::partition(first, last, [](const Data n) { return n < 0; });
    mask = get_mask(first, middle);
    if (mask) { radix_sort_msd1b_impl(first, middle, mask, 1 << msb(mask)); }
    mask = get_mask(middle, last);
    if (mask) { radix_sort_msd1b_impl(middle, last, mask, 1 << msb(mask)); }
  }
}

// Radix sort (LSD by 4 bits)
void radix_sort_lsd4b(DataIter first, DataIter last)
{
  using UData = std::make_unsigned<Data>::type;
#ifdef ARRAY_SIGNED_VALUES
  constexpr UData add = static_cast<UData>(INT_MIN);
#else
  constexpr UData add = 0;
#endif
  constexpr unsigned radix = 4, width = sizeof(UData) * CHAR_BIT, mask = (1 << radix) - 1;
  std::vector<Data> dest(std::distance(first, last));
  DataIter first2 = dest.begin(), last2 = dest.end();
  std::vector<size_t> counts(1 << radix);
  // Main loop
  for (unsigned shift = 0; shift < width; shift += radix) {
    if (shift) { std::fill(counts.begin(), counts.end(), 0); }
    // Next three loops implement counting sort
    for_each(first, last, [&](const auto el) { ++counts[((el+add) >> shift) & mask]; });
    size_t idx = 0;
    for (auto& el : counts) { const size_t temp = el; el = idx; idx += temp; }
    for_each(first, last, [&](const auto el) { *std::next(first2, counts[((el+add) >> shift) & mask]++) = el; });
    std::swap(first, first2);
    std::swap(last, last2);
  }
}

// Radix sort (LSD by 8 bits)
void radix_sort_lsd8b(DataIter first, DataIter last)
{
  using UData = std::make_unsigned<Data>::type;
#ifdef ARRAY_SIGNED_VALUES
  constexpr UData add = static_cast<UData>(INT_MIN);
#else
  constexpr UData add = 0;
#endif
  constexpr unsigned radix = 8, width = sizeof(UData) * CHAR_BIT, mask = (1 << radix) - 1;
  std::vector<Data> dest(std::distance(first, last));
  DataIter first2 = dest.begin(), last2 = dest.end();
  std::vector<size_t> counts(1 << radix);
  // Main loop
  for (unsigned shift = 0; shift < width; shift += radix) {
    if (shift) { std::fill(counts.begin(), counts.end(), 0); }
    // Next three loops implement counting sort
    for_each(first, last, [&](const auto el) { ++counts[((el+add) >> shift) & mask]; });
    size_t idx = 0;
    for (auto& el : counts) { const size_t temp = el; el = idx; idx += temp; }
    for_each(first, last, [&](const auto el) { *std::next(first2, counts[((el+add) >> shift) & mask]++) = el; });
    std::swap(first, first2);
    std::swap(last, last2);
  }
}

// Radix sort (LSD by 8 bits, modified)
void radix_sort_lsd8b_mod(DataIter first, DataIter last)
{
  using UData = std::make_unsigned<Data>::type;
#ifdef ARRAY_SIGNED_VALUES
  constexpr UData add = static_cast<UData>(INT_MIN);
#else
  constexpr UData add = 0;
#endif
  constexpr unsigned radix = 8, width = sizeof(UData) * CHAR_BIT, count_blocks = width / radix, cb_size = 1 << radix, mask = cb_size - 1;
  static_assert(width == 32, "This functions is designed for 32-bit integers!");
  std::vector<Data> temp(std::distance(first, last));
  DataIter first2 = temp.begin(), last2 = temp.end();
  std::vector<size_t> counts(cb_size * count_blocks);
  // Prepare counters
  for_each(first, last, [&](const auto el) {
    ++counts[  el                 & mask];
    ++counts[( el      >> radix*1 & mask) + cb_size*1];
    ++counts[( el      >> radix*2 & mask) + cb_size*2];
    ++counts[((el+add) >> radix*3)        + cb_size*3];
  });
  // Converting counters to indexes
  for (auto it = counts.begin(); it != counts.end(); ) {
    size_t idx = 0;
    for (auto it_end = it + cb_size; it != it_end; ++it) {
      const size_t el = *it; *it = idx; idx += el;
    }
  }
  // Sort
  for_each(first, last,   [&](const auto el) { *std::next(first2, counts[  el                  & mask             ]++) = el; });
  for_each(first2, last2, [&](const auto el) { *std::next(first,  counts[((el      >> radix*1) & mask) + cb_size*1]++) = el; });
  for_each(first, last,   [&](const auto el) { *std::next(first2, counts[((el      >> radix*2) & mask) + cb_size*2]++) = el; });
  for_each(first2, last2, [&](const auto el) { *std::next(first,  counts[((el+add) >> radix*3)         + cb_size*3]++) = el; });
}

// Counting sort, returns false if range of numbers > COUNTING_SORT_MAX_RANGE
bool counting_sort(DataIter first, const DataIter last)
{
  auto minmax_it = std::minmax_element(first, last);
  const Data min_el = *std::get<0>(minmax_it), max_el = *std::get<1>(minmax_it);
  const Data range = max_el - min_el + 1;
  if (range > COUNTING_SORT_MAX_RANGE) { return false; }
  vector<Data> count(range, 0);
  for_each(first, last, [&count, min_el](const Data n) {
    ++count[n - min_el];
  });
  for (Data n = min_el; n <= max_el; ++n) {
    size_t count_n = count[n - min_el];
    if (count_n > 0) { first = std::fill_n(first, count_n, n); }
  }
  return true;
}

// Counting sort using map
void counting_sort_map(DataIter first, const DataIter last)
{
  std::unordered_map<Data, size_t> count_map;
  for_each(first, last, [&count_map](const Data n) {
    ++count_map[n];
  });

  std::vector<std::pair<Data, size_t>> count(count_map.begin(), count_map.end());
  std::sort(count.begin(), count.end(), [](const auto& a, const auto& b) { return a.first < b.first; });

  for_each(count.begin(), count.end(), [count, &first](const auto& el) {
    first = std::fill_n(first, el.second, el.first);
  });
}

// Counting sort using ordered map (very slow!)
void counting_sort_orderedmap(DataIter first, const DataIter last)
{
  std::map<Data, size_t> count_map;
  for_each(first, last, [&count_map](const Data n) {
    ++count_map[n];
  });

  for_each(count_map.begin(), count_map.end(), [count_map, &first](const auto& el) {
    first = std::fill_n(first, el.second, el.first);
  });
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Sort, time measure and check
double sort_measure_check(vector<Data> a, const vector<Data>& ok, std::function<void(DataIter, DataIter)> sort_func, bool display = true)
{
  // Sorting
  auto start_time = std::chrono::steady_clock::now();
  sort_func(a.begin(), a.end());
  std::chrono::duration<double> total_time = std::chrono::steady_clock::now() - start_time;
  double time = total_time.count();
  if (display) {
    cout << "Elapsed time: " << time << " sec\n"
            "Checking...";
  }

  // Checking
  if (display) {
    if (a == ok) {
      cout << " successfully sorted!\n";
    } else {
      cout << " sort is *FAILED*!\n";
    }
  }

  return time;
}

int main()
{
  // Generating an array
  vector<Data> array, array_ok;
  std::random_device rd;
  std::mt19937 re(rd());
  std::uniform_int_distribution<Data> random(ARRAY_RAND_MIN, ARRAY_RAND_MAX);
  for (size_t i = 0; i < ARRAY_SIZE; ++i) {
    array.push_back(random(re));
  }
  array_ok = array;
  sort(array_ok.begin(), array_ok.end());

  cout << std::fixed;

  // Sorting, measuring and testing
  cout << "\nBubble sorting...\n";
  double time_bubble = sort_measure_check(array, array_ok, bubble_sort);
/*
  cout << "\nInsertion-bubble combined sorting...\n";
  sort_measure_check(array, array_ok, insbubble_sort);  // sometimes crashes :(
*/
  cout << "\nStraight insertion sorting...\n";
  double time_insertion = sort_measure_check(array, array_ok, insertion_sort);

  cout << "\nBinary insertion sorting...\n";
  double time_binins = sort_measure_check(array, array_ok, binins_sort);

  cout << "\nQuick sorting...\n";
  double time_quick = sort_measure_check(array, array_ok, quick_sort);

  cout << "\nCombined (quick-insertion) sorting...\n";
  sort_measure_check(array, array_ok, quickins_sort);

  cout << "\nRadix (MSD/1bit) sorting...\n";
  sort_measure_check(array, array_ok, radix_sort_msd1b);

  cout << "\nRadix (LSD/4bit) sorting...\n";
  sort_measure_check(array, array_ok, radix_sort_lsd4b);

  cout << "\nRadix (LSD/8bit) sorting...\n";
  sort_measure_check(array, array_ok, radix_sort_lsd8b);

  cout << "\nRadix (LSD/8bit, modified) sorting...\n";
  sort_measure_check(array, array_ok, radix_sort_lsd8b_mod);

  cout << "\nCounting sorting...\n";
  sort_measure_check(array, array_ok, counting_sort);

  cout << "\nCounting (unordered map) sorting...\n";
  sort_measure_check(array, array_ok, counting_sort_map);

  cout << "\nCounting (ordered map) sorting...\n";
  sort_measure_check(array, array_ok, counting_sort_orderedmap);

  cout << "\nSTL sorting...\n";
  sort_measure_check(array, array_ok, std::move(std::sort<DataIter>));

  cout << "\nSTL stable sorting...\n";
  sort_measure_check(array, array_ok, std::move(std::stable_sort<DataIter>));

  cout << "\nPress Enter to show comparation and start extra test for fast sorts (huge arrays)...";
  std::cin.get();

  // Comparing
  cout << "\nBubble/straight insertion sort time ratio: " << time_bubble / time_insertion;
  cout << "\nBubble/binary insertion sort time ratio: " << time_bubble / time_binins;
  cout << "\nStraight/binary insertion sort time ratio: " << time_insertion / time_binins;
  cout << "\nStraight insertion/quick sort time ratio: " << time_insertion / time_quick;
  cout << "\nBinary insertion/quick sort time ratio: " << time_binins / time_quick;
  cout << "\n\n";

  // Fast sorts comparing
  for (size_t i = 0; i < ARRAY_HUGE_SIZE; ++i) {
    array.push_back(random(re));
  }
  array_ok = array;
  sort(array_ok.begin(), array_ok.end());

  time_quick = sort_measure_check(array, array_ok, quick_sort, false);
  cout << "Quick sort time: " << time_quick << " sec\n";

  double time = sort_measure_check(array, array_ok, quickins_sort, false);
  cout << "Quick-insertion sort time: " << time << " sec [quick/quick-insertion sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, radix_sort_msd1b, false);
  cout << "Radix (MSD/1bit) sort time: " << time << " sec [quick/radix_msd1b sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, radix_sort_lsd4b, false);
  cout << "Radix (LSD/4bit) sort time: " << time << " sec [quick/radix_lsd4b sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, radix_sort_lsd8b, false);
  cout << "Radix (LSD/8bit) sort time: " << time << " sec [quick/radix_lsd8b sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, radix_sort_lsd8b_mod, false);
  cout << "Radix (LSD/8bit, modified) sort time: " << time << " sec [quick/radix_lsd8b_mod sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, counting_sort, false);
  cout << "Counting sort time: " << time << " sec [quick/counting sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, counting_sort_map, false);
  cout << "Counting sort (unordered map) time: " << time << " sec [quick/counting sort (with map) time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, counting_sort_orderedmap, false);
  cout << "Counting sort (ordered map) time: " << time << " sec [quick/counting sort (with ordered map) time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, std::move(std::sort<DataIter>), false);
  cout << "STL sort time: " << time << " sec [quick/STL sort time ratio: " << time_quick / time << "]\n";

  time = sort_measure_check(array, array_ok, std::move(std::stable_sort<DataIter>), false);
  cout << "Stable STL sort time: " << time << " sec [quick/stable STL sort time ratio: " << time_quick / time << "]\n";

  return 0;
}

VC++2019 (64-bit) results:

Bubble sorting...
Elapsed time: 5.760899 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 3.301789 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.626306 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.003945 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.003795 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004372 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.000973 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.012931 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.022677 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.004187 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.003631 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 9.198216
Insertion/quick sort time ratio: 158.767517

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 0.949962 sec
Quick-insertion sort time: 1.007622 sec [quick/quick-insertion sort time ratio: 0.942776]
Radix sort time: 1.012636 sec [quick/radix sort time ratio: 0.938108]
Counting sort time: 0.087769 sec [quick/counting sort time ratio: 10.823416]
Counting sort (map) time: 0.424622 sec [quick/counting sort (with map) time ratio: 2.237191]
Counting sort (ordered map) time: 3.348882 sec [quick/counting sort (with map) time ratio: 0.283665]
STL sort time: 1.134262 sec [quick/STL sort time ratio: 0.837515]
Stable STL sort time: 1.303425 sec [quick/stable STL sort time ratio: 0.728819]

----------------------------------------

VC++2019 (32-bit) results:

Bubble sorting...
Elapsed time: 6.083628 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 3.375193 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.635745 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.004232 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.003794 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004916 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.001029 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.012712 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.020907 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.004624 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.004019 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 9.569296
Insertion/quick sort time ratio: 150.233854

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 0.943157 sec
Quick-insertion sort time: 0.941727 sec [quick/quick-insertion sort time ratio: 1.001518]
Radix sort time: 1.090758 sec [quick/radix sort time ratio: 0.864680]
Counting sort time: 0.095926 sec [quick/counting sort time ratio: 9.832101]
Counting sort (map) time: 0.291345 sec [quick/counting sort (with map) time ratio: 3.237257]
Counting sort (ordered map) time: 2.818296 sec [quick/counting sort (with map) time ratio: 0.334655]
STL sort time: 1.225816 sec [quick/STL sort time ratio: 0.769412]
Stable STL sort time: 1.407950 sec [quick/stable STL sort time ratio: 0.669880]

G++ (MinGW, 64-bit) results:

Bubble sorting...
Elapsed time: 6.374747 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 3.262074 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.859826 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.004498 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.003753 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004339 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.000702 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.010720 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.023904 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.004132 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.003925 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 7.413996
Insertion/quick sort time ratio: 191.165903

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 1.049459 sec
Quick-insertion sort time: 1.015772 sec [quick/quick-insertion sort time ratio: 1.033164]
Radix sort time: 1.012416 sec [quick/radix sort time ratio: 1.036590]
Counting sort time: 0.082723 sec [quick/counting sort time ratio: 12.686460]
Counting sort (map) time: 0.685396 sec [quick/counting sort (with map) time ratio: 1.531174]
Counting sort (ordered map) time: 3.423327 sec [quick/counting sort (with map) time ratio: 0.306561]
STL sort time: 1.022013 sec [quick/STL sort time ratio: 1.026856]
Stable STL sort time: 1.356755 sec [quick/stable STL sort time ratio: 0.773507]

----------------------------------------

G++ (MinGW, 32-bit) results:

Bubble sorting...
Elapsed time: 6.234558 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 3.187109 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.623302 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.004080 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.004767 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004653 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.000751 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.011480 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.021483 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.003475 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.004748 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 10.002472
Insertion/quick sort time ratio: 152.781258

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 0.979387 sec
Quick-insertion sort time: 1.037273 sec [quick/quick-insertion sort time ratio: 0.944193]
Radix sort time: 0.995465 sec [quick/radix sort time ratio: 0.983848]
Counting sort time: 0.085438 sec [quick/counting sort time ratio: 11.463113]
Counting sort (map) time: 0.379395 sec [quick/counting sort (with map) time ratio: 2.581444]
Counting sort (ordered map) time: 2.521386 sec [quick/counting sort (with map) time ratio: 0.388432]
STL sort time: 1.029249 sec [quick/STL sort time ratio: 0.951554]
Stable STL sort time: 1.468098 sec [quick/stable STL sort time ratio: 0.667113]

Clang (64-bit) results:

Bubble sorting...
Elapsed time: 4.635505 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 2.525102 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.641659 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.003840 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.003408 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004325 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.001016 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.013753 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.023928 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.004129 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.003847 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 7.224247
Insertion/quick sort time ratio: 167.085722

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 0.874214 sec
Quick-insertion sort time: 0.881937 sec [quick/quick-insertion sort time ratio: 0.991243]
Radix sort time: 0.991927 sec [quick/radix sort time ratio: 0.881328]
Counting sort time: 0.090409 sec [quick/counting sort time ratio: 9.669500]
Counting sort (map) time: 0.511668 sec [quick/counting sort (with map) time ratio: 1.708555]
Counting sort (ordered map) time: 3.374957 sec [quick/counting sort (with map) time ratio: 0.259030]
STL sort time: 1.145496 sec [quick/STL sort time ratio: 0.763175]
Stable STL sort time: 1.379499 sec [quick/stable STL sort time ratio: 0.633718]

----------------------------------------

Clang (32-bit) results:

Bubble sorting...
Elapsed time: 5.468504 sec
Checking... successfully sorted!

Insertion-bubble combined sorting...
Elapsed time: 2.877002 sec
Checking... successfully sorted!

Insertion sorting...
Elapsed time: 0.613666 sec
Checking... successfully sorted!

Quick sorting...
Elapsed time: 0.004283 sec
Checking... successfully sorted!

Combined (quick-insertion) sorting...
Elapsed time: 0.003543 sec
Checking... successfully sorted!

Radix sorting...
Elapsed time: 0.004312 sec
Checking... successfully sorted!

Counting sorting...
Elapsed time: 0.000830 sec
Checking... successfully sorted!

Counting (map) sorting...
Elapsed time: 0.011564 sec
Checking... successfully sorted!

Counting (ordered map) sorting...
Elapsed time: 0.019331 sec
Checking... successfully sorted!

STL sorting...
Elapsed time: 0.004460 sec
Checking... successfully sorted!

STL stable sorting...
Elapsed time: 0.004160 sec
Checking... successfully sorted!

Bubble/insertion sort time ratio: 8.911202
Insertion/quick sort time ratio: 143.282892

Press Enter to start extra test for fast sorts (huge arrays)...
Quick sort time: 0.870513 sec
Quick-insertion sort time: 0.909650 sec [quick/quick-insertion sort time ratio: 0.956976]
Radix sort time: 1.032305 sec [quick/radix sort time ratio: 0.843271]
Counting sort time: 0.092751 sec [quick/counting sort time ratio: 9.385442]
Counting sort (map) time: 0.369344 sec [quick/counting sort (with map) time ratio: 2.356915]
Counting sort (ordered map) time: 2.254671 sec [quick/counting sort (with map) time ratio: 0.386093]
STL sort time: 1.172021 sec [quick/STL sort time ratio: 0.742745]
Stable STL sort time: 1.444928 sec [quick/stable STL sort time ratio: 0.602461]