Sorting can be done faster than quadratic time. Two of such sorting algorithms are based on the principle of divide and conquer. Divide and conquer is a strategy that helps simplify solving a complex problem. It begins by dividing a problem into sub-problems. It then keeps doing that until sub-problems are trivial to solve. In the end, outcomes of all sub-problems are assembled backwards, which eventually gives the final result of the whole problem.
Sorting algorithms are useful and commonly used for the pre-processing of a data set. Here we look at three simply sorting algorithms that have a quadratic time complexity. We also visit the property of each of them, in particular, the stability of sorting algorithms.
Morris traversal does not need to rely on recursion or stacks. Instead, it reorganize the tree into a thread that forms a certain sequence. It does modify the structure of the original tree. When that is not a concern, Morris traversal is able to achieve the optimal time and space complexity. Morris traversal is original designed for in-order traversal, but it can be applied to pre-order traversal as well, though I am not sure if it’s applicable to post-order traversal.
Binary tree traversal is a perfect case to show the power of recursive algorithms which enable straightforward and trivial implementations of all three traversal styles (in-order, pre-order, and post-order). Given its simplicity, recursion is not the focus of this article. Instead, we are looking into how to do it iteratively.
When traversing a graph, one typical question we are interested in is whether the graph contains cycles. For directed graphs, a cycle often indicates the conflict between dependencies. There are two approaches to traverse a graph and identify cycles, the breadth-first and depth-first searches.
When dealing with arrays or lists, we tend to think in the single-threaded way and scan the array or list with one pointer. Sometimes working concurrently through two pointers can help make things more clear and efficient. For example, problems can thus be solved within one pass instead of two. In some cases, solutions can also involve much less space usage.
Versioning can be used to support the isolation among transactions via snapshotting (i.e., snapshot isolation level). While one transaction is editing the data, the other transactions should only be able to see the original data before the edit. In order to achieve that, both of the original and new data are kept. That is, we maintain versions of the data.
The unique benefit of snapshot isolation is to allow a great concurrency with the execution of multiple transactions. This is because readers do not block writers and writers do not block readers. The rationale behind that is a well-designed mechanism of versioning, including the version generation, visibility, and reclamation.
A transaction must be always consistent and durable. This is straightforward when everything is normal, whereas maintaining such properties despite of failures becomes nontrivial. Failures like system crashes can leave a system in an inconsistent state. Today we are treating failures as the norm. It’s critical to possess the capability of fault tolerance. One important remedy is to recover transactions after crashes.
While transactions desires isolation, too strong isolation may offset the performance benefit from execution concurrency. In practice, isolation is defined at different levels with trade-offs between consistency and concurrency. The applicability of each isolation level is determined by the specific scenario targeted.