README.en.md

💎 Crystal Sort

Data sorting based on data partitioning into intervals.
Works for whole cisels in the range [0; +inf)
⏳ Average Time: O(n log n)
💾 Average Memory: O(n)

📖 Languages

🇷🇺 Русский (Russian) - README.md

📊 Complexity Analysis (Big O)

📐 Theoretical assessment

This estimate is based on a mathematical analysis of the logic of the Crystal Sort algorithm.

• The best time: O(n) — the array is sorted (thanks to the initial check).
• Average time: O(n log n) — when the data is evenly distributed. The dynamic coefficient k allows you to balance the spread of data, which leads to a logarithmic depth of recursion.
• The worst time: O(n2) — occurs when all the elements fall into the same group.
• Memory costs: O(n) — storing the partitioning table `geode'.

🌐 Big O Calc

Big O Notation Score (https://www.bigocalc.com). The results of automated tools are evaluative and may depend on the testing method.
The function crystal_sort performs a recursive sorting process with the following characteristics:

⏳ Time Complexity:

• The initial check to see if the array is already sorted takes O(n).
• The calculation of k involves constant time operations.
• Building the geode dictionary involves iterating over all elements once, which is O(n).
• The recursive calls are made on subarrays (cryst), which partition the original array based on the value of cryst_idx = x // k.
• In the worst case, if the array elements are distributed unevenly, the recursion depth could be proportional to the number of elements, leading to a worst-case complexity similar to O(n²).
• If the array is uniformly distributed, the recursion depth reduces, and the average case tends toward O(n log n).

Overall, the worst-case time complexity is approximately O(n²), but average cases may approach O(n log n).

💾 Space Complexity:

• The geode dictionary stores references to subarrays, which collectively hold all elements, so it uses O(n) space.
• The recursion stack depth depends on how the array is partitioned; in the worst case, it can be O(n).
• Additional variables (mx_cryst, k, etc.) use constant space.

Therefore, the overall space complexity is O(n), dominated by the storage of the input and auxiliary data structures.

🐍 Python implementation

def crystal_sort(arr):
    # Checking whether the array is O(n) sorted
    for i in range(1, len(arr)):
        if arr[i - 1] > arr[i]:
            break
    # If it is sorted, we return the array
    else:
        return arr

    # Partition coefficient
    ln = len(arr)
    k = (min(arr) * (ln - 1) + max(arr)) // ln + 1

    # The partition table
    geode = {}
    mx_cryst = -1

    # The formation of the partition table is O(n). We distribute the numbers depending on k
    for x in arr:
        cryst_idx = x // k
        geode[cryst_idx] = geode.get(cryst_idx, []) + [x]
        mx_cryst = max(mx_cryst, cryst_idx)

    # Recursively sorting each row of the division table ("crystals")
    pos = 0
    for b in range(mx_cryst + 1):
        if b not in geode:
            continue
        cryst = geode[b]
        for el in crystal_sort(cryst):
            arr[pos] = el
            pos += 1

    return arr

👴 C++ implementation

void crystal_sort(vector<int>& arr) {
	/* Checking whether the array is O(n) sorted */
	bool sorted = true;
	for (int i = 1; i < arr.size(); i++)
		if (arr[i - 1] > arr[i]) {
			sorted = false;
			break;
		}
	/* If it is sorted, we return the array */
	if (sorted) return;

	/* Partition coefficient */
    long long min_val = *min_element(arr.begin(), arr.end());
    long long max_val = *max_element(arr.begin(), arr.end());
    size_t n = arr.size();

    long long k = (min_val * (n - 1) + max_val) / n + 1;
    if (k <= 0) k = 1;

	/* The partition table */
    unordered_map<int, vector<int>> geode;
    int mx_cryst = -1;

	/* The formation of the partition table is O(n). We distribute the numbers depending on k */
    for (int x : arr) {
        int cryst_idx = x / k;
        geode[cryst_idx].push_back(x);
        if (cryst_idx > mx_cryst) mx_cryst = cryst_idx;
    }

	/* Recursively sorting each row of the division table ("crystals") */
    size_t pos = 0;
    for (int b = 0; b <= mx_cryst; ++b) {
        auto cryst = geode.find(b);
        if (cryst != geode.end()) {
            crystal_sort(cryst->second);
            for (int val : cryst->second)
                arr[pos++] = val;
        }
    }
}