What's the most efficient way to construct a new, sorted, array?

Question

Background

Most questions around sorting talk about sorting an existing unsorted array. Is constructing a new array in a sorted order an equivalent problem or a different one? Here's an example that will clear things up:

Example

I'm generating N random numbers and want to insert them into a new array as I generate them, and I want the final array to be sorted.

Possible Solutions

Insertion Sort

My gut told me that putting each element in the correct place as it's generated would be fastest. This is accomplished by doing a binary search to find the correct point in the array to insert the new element. However, this is an insertion sort, which is known to be less efficient on large lists than other sorting algorithms.

Quicksort

Quicksort is generally thought of as the most efficient 'general' sorting algorithm, where nothing is known about the inputs to the array, and it's more efficient than insertion sort on large lists. Would it, therefore, be best to simply put the random numbers in the array in an unsorted order, and then sort them at the end with quicksort?

Other Solutions

Is there another algorithm I haven't thought of?

Answer 1

TimeSort Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort. It was designed to perform well on many kinds of real-world data. Timsort was invented by Tim Peters in 2002 and is the default sorting algorithm in various programming languages and libraries, including Python.

The algorithm works by dividing the input array into small subarrays, which are individually sorted using insertion sort. Then, these sorted subarrays are merged together using a modified merge sort algorithm. The key idea behind Timsort is to take advantage of the existing order in the input data to minimize the number of comparisons and improve performance.

Here's a high-level overview of how Timsort works:

1. Divide the input array into small subarrays called "runs." A run is a sequence of elements that are already sorted or have a natural order.

2. Use insertion sort to sort each run individually. This step takes advantage of the fact that small arrays are often already partially sorted.

3. Merge the sorted runs together using a modified merge sort algorithm. The merge operation combines two runs into a larger, sorted run.

4. Repeat steps 1-3 until the entire array is sorted.

Timsort has several advantages over other sorting algorithms. It performs well on many kinds of data, including data with natural ordering or partially sorted data. It also has a stable sorting behavior, meaning that elements with equal values maintain their relative order in the sorted output. This property is particularly useful when sorting complex data structures that have multiple keys.

Overall, Timsort is a highly efficient and widely-used sorting algorithm known for its versatility and good performance characteristics in various scenarios.

The runtime complexity of Timsort is O(n log n) in the worst case, where "n" is the number of elements to be sorted. However, in practice, Timsort often exhibits better performance than other sorting algorithms, especially when dealing with real-world data.

The reason for the improved performance is that Timsort takes advantage of existing order in the input data. It identifies and merges already sorted subsequences (runs), reducing the number of comparisons needed during the merge step.

In the best-case scenario, where the input data is already sorted or has a significant amount of pre-existing order, Timsort can achieve a runtime complexity of O(n). This is because it can detect the sorted runs and simply perform the merging step without any additional sorting.

On average, Timsort performs better than other popular sorting algorithms, such as quicksort or merge sort, because it adapts its strategy based on the characteristics of the input data. It performs well on both small and large datasets and is particularly efficient when the data has partially sorted regions.

Runtime It's worth noting that the actual runtime of Timsort can also be influenced by factors such as the hardware, programming language implementation, and specific optimizations applied to the algorithm. However, the worst-case and average-case time complexities mentioned above provide a general understanding of the performance characteristics of Timsort.

Answer 2

Most questions around sorting talk about sorting an existing unsorted array. Is constructing a new array in a sorted order an equivalent problem or a different one? 

It boils down to the same problem for random data, due to efficiency considerations.

Given random data, it's actually more efficient to first generate the random values into an array (unsorted) - O(n) time complexity - and then sort it with your favorite O(n log n) sort algorithm, making the entire operation O(2n log n) time complexity, and, depending on sort algorithm used, between O(1) and O(n) space complexity.

There is no way to beat that approach by "keeping an array sorted as it's constructed" for random data, because any approach will require exactly O(n) generations/insertions of the values, and at least O(n log n) comparisons/swaps/shifts - no matter which method, from the numerous mentioned in comments on the original question, is used. Note, as per a very useful comment on my original answer, the binary insertion sort variant suggested in the original question will likely degrade to O(n^2) time complexity, making it an inferior solution to just generating an array of values first and then sorting it.

Using a balanced tree just matches the time complexity of generating an array and then sorting it - but loses in space complexity, as trees have some overhead, compared to an array, to keep track of child nodes, etc. Also of note, trees are heap-allocated, and require a pointer dereference operation for accessing any child node - so even though the Big-O time complexity is equivalent to first generating an array of data and then sorting it, the real performance of the tree solution will be worse, as there's no data locality, and there's extra cost of pointer dereference. An additional consideration on balanced trees is that insertion cost into something like an AVL is quite high - that is, the n in AVL's O(n log n) insertion is not the same cost as n in an in-place sort of an array, due to necessary rotations of tree nodes to achieve balance. Just because Big-O is the same doesn't mean performance is the same. Even if you have an absolute need to be able to grab the data in a sorted order at some point during construction of the array, it might still be cheaper to just sort an array as you need it, unless you need it sorted at each insertion!

Note, this answer pertains to random data - it is possible, and even likely, to come up with a more efficient approach for "keeping an array sorted as it's constructed" if both the size and characteristics of the data are known, and follow some mathematical pattern, other than randomness; however, such approach would necessarily be overfit for the specific data set it relates to, rather than a general solution.

Answer 3

If you want a true O(nlogn) and sorted "as it is constructed", I would recommend using a proper (tree) based data structure instead of array. You can use data structures like self balanced binary tree, AVL trees.

Answer 4

I recommend the Heapsort or Mergesort.

Heapsort is a comparison-based algorithm that uses a binary heap data structure to sort elements. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

Mergesort is a comparison-based algorithm that focuses on how to merge together two pre-sorted arrays such that the resulting array is also sorted.