2016-01-07 17:14:33 +09:00
|
|
|
#pragma once
|
2010-08-09 22:28:56 +09:00
|
|
|
|
2012-01-15 17:29:57 +09:00
|
|
|
#include <algorithm>
|
2010-08-09 22:28:56 +09:00
|
|
|
#include <nall/utility.hpp>
|
|
|
|
|
|
|
|
//class: merge sort
|
|
|
|
//average: O(n log n)
|
|
|
|
//worst: O(n log n)
|
|
|
|
//memory: O(n)
|
|
|
|
//stack: O(log n)
|
|
|
|
//stable?: yes
|
|
|
|
|
2012-01-26 15:50:09 +09:00
|
|
|
//note: merge sort was chosen over quick sort, because:
|
|
|
|
//* it is a stable sort
|
|
|
|
//* it lacks O(n^2) worst-case overhead
|
2018-08-21 12:17:12 +09:00
|
|
|
//* it usually runs faster than quick sort anyway
|
2012-01-26 15:50:09 +09:00
|
|
|
|
2018-08-21 12:17:12 +09:00
|
|
|
//note: insertion sort is generally more performant than selection sort
|
|
|
|
#define NALL_MERGE_SORT_INSERTION
|
|
|
|
//#define NALL_MERGE_SORT_SELECTION
|
2010-08-09 22:28:56 +09:00
|
|
|
|
|
|
|
namespace nall {
|
|
|
|
|
2021-02-08 18:11:00 +09:00
|
|
|
template<typename T, typename Comparator> auto sort(T list[], u32 size, const Comparator& lessthan) -> void {
|
2013-05-02 20:25:45 +09:00
|
|
|
if(size <= 1) return; //nothing to sort
|
|
|
|
|
2018-08-21 12:17:12 +09:00
|
|
|
//sort smaller blocks using an O(n^2) algorithm (which for small sizes, increases performance)
|
2013-05-02 20:25:45 +09:00
|
|
|
if(size < 64) {
|
2018-08-21 12:17:12 +09:00
|
|
|
//insertion sort requires a copy (via move construction)
|
|
|
|
#if defined(NALL_MERGE_SORT_INSERTION)
|
2021-02-08 18:11:00 +09:00
|
|
|
for(s32 i = 1, j; i < size; i++) {
|
2022-09-13 16:47:47 +09:00
|
|
|
T copy(std::move(list[i]));
|
2013-05-02 20:25:45 +09:00
|
|
|
for(j = i - 1; j >= 0; j--) {
|
|
|
|
if(!lessthan(copy, list[j])) break;
|
2022-09-13 16:47:47 +09:00
|
|
|
list[j + 1] = std::move(list[j]);
|
2012-01-26 15:50:09 +09:00
|
|
|
}
|
2022-09-13 16:47:47 +09:00
|
|
|
list[j + 1] = std::move(copy);
|
2013-05-02 20:25:45 +09:00
|
|
|
}
|
2018-08-21 12:17:12 +09:00
|
|
|
//selection sort requires a swap
|
|
|
|
#elif defined(NALL_MERGE_SORT_SELECTION)
|
2021-02-08 18:11:00 +09:00
|
|
|
for(u32 i = 0; i < size; i++) {
|
|
|
|
u32 min = i;
|
|
|
|
for(u32 j = i + 1; j < size; j++) {
|
2013-05-02 20:25:45 +09:00
|
|
|
if(lessthan(list[j], list[min])) min = j;
|
2010-08-09 22:28:56 +09:00
|
|
|
}
|
2018-08-21 12:17:12 +09:00
|
|
|
if(min != i) swap(list[i], list[min]);
|
2010-08-09 22:28:56 +09:00
|
|
|
}
|
2013-05-02 20:25:45 +09:00
|
|
|
#endif
|
|
|
|
return;
|
|
|
|
}
|
2010-08-09 22:28:56 +09:00
|
|
|
|
2013-05-02 20:25:45 +09:00
|
|
|
//split list in half and recursively sort both
|
2021-02-08 18:11:00 +09:00
|
|
|
u32 middle = size / 2;
|
2013-05-02 20:25:45 +09:00
|
|
|
sort(list, middle, lessthan);
|
|
|
|
sort(list + middle, size - middle, lessthan);
|
2010-08-09 22:28:56 +09:00
|
|
|
|
2013-05-02 20:25:45 +09:00
|
|
|
//left and right are sorted here; perform merge sort
|
2018-08-21 12:17:12 +09:00
|
|
|
//use placement new to avoid needing T to be default-constructable
|
|
|
|
auto buffer = memory::allocate<T>(size);
|
2021-02-08 18:11:00 +09:00
|
|
|
u32 offset = 0, left = 0, right = middle;
|
2013-05-02 20:25:45 +09:00
|
|
|
while(left < middle && right < size) {
|
|
|
|
if(!lessthan(list[right], list[left])) {
|
2022-09-13 16:47:47 +09:00
|
|
|
new(buffer + offset++) T(std::move(list[left++]));
|
2013-05-02 20:25:45 +09:00
|
|
|
} else {
|
2022-09-13 16:47:47 +09:00
|
|
|
new(buffer + offset++) T(std::move(list[right++]));
|
2010-08-09 22:28:56 +09:00
|
|
|
}
|
|
|
|
}
|
2022-09-13 16:47:47 +09:00
|
|
|
while(left < middle) new(buffer + offset++) T(std::move(list[left++]));
|
|
|
|
while(right < size ) new(buffer + offset++) T(std::move(list[right++]));
|
2013-05-02 20:25:45 +09:00
|
|
|
|
2021-02-08 18:11:00 +09:00
|
|
|
for(u32 i = 0; i < size; i++) {
|
2022-09-13 16:47:47 +09:00
|
|
|
list[i] = std::move(buffer[i]);
|
2018-08-21 12:17:12 +09:00
|
|
|
buffer[i].~T();
|
|
|
|
}
|
|
|
|
memory::free(buffer);
|
2013-05-02 20:25:45 +09:00
|
|
|
}
|
|
|
|
|
2021-02-08 18:11:00 +09:00
|
|
|
template<typename T> auto sort(T list[], u32 size) -> void {
|
2013-05-02 20:25:45 +09:00
|
|
|
return sort(list, size, [](const T& l, const T& r) { return l < r; });
|
|
|
|
}
|
2012-01-26 15:50:09 +09:00
|
|
|
|
2010-08-09 22:28:56 +09:00
|
|
|
}
|