Meaning and mechanism
Sorting is the process of rearranging data according to a given order. Bubble sort compares adjacent elements, and merge sort utilizes a structure that combines divided lists.
The iterative structure of an algorithm determines how much the workload increases as the input size grows. Even with the same size, the initial order and the termination conditions of the implementation can change the results.
Relationships and conditions
The comparative scale for a typical bubble sort is O(n²), while merge sort has a scale of O(n log n). It is important to note that a specific number of comparisons and asymptotic notation O are not the same thing.
The experiment is not a benchmark that counts the number of value comparisons, exchanges, and writes to measure the actual time of a computer. It does not treat data writes and position swaps as the same operation.
What to observe in the simulation
Comparison counts depend on size, initial order, and algorithm.
We count value comparisons and swaps rather than elapsed time. Merge writes are separate.
Key relationships and symbols
bubble: n(n−1)/2 · merge: O(n log₂n)
| Symbol | Meaning | Unit |
|---|---|---|
| n | Number of input data items | items |
| O(n log n) | Upper bound expression of asymptotic growth according to input size. | Complexity |
Worked example
Are merge writes and swaps the same operation?
Different operations · Comparison counts depend on size, initial order, and algorithm.
Common misconceptions
- The fact that the number of comparisons is small does not mean that all computers and inputs will actually shorten in the same proportion in terms of time.