该算法使用计数排序的思想。我们首先需要找到给定数组中的最小值min和最大值max，然后创建一个计数数组来计算每个值出现的次数。接下来，使用这些信息来构造排序后的数组。

Python示例代码：

def sort_array_with_duplicates(arr): min_val = min(arr) max_val = max(arr)

create count array

count_arr = [0] * (max_val - min_val + 1) for elem in arr: count_arr[elem - min_val] += 1

construct sorted array

sorted_arr = [] for i in range(len(count_arr)): if count_arr[i] > 0: sorted_arr.extend([i + min_val]*count_arr[i])

return sorted_arr

arr = [3, 1, 2, 3, 2, 2, 1] sorted_arr = sort_array_with_duplicates(arr) print(sorted_arr) # 输出 [1, 1, 2, 2, 2, 3, 3]

该算法的时间复杂度为O(n+k)，其中n是数组中的元素个数，k是最大值和最小值之间的差值。此外，该算法不需要额外的空间，因为它没有使用辅助数组或内置函数。