Study guide
6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency
Praxis Computer Science 5652
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode
1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy
2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects
2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations
3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security
3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage
4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation
4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing
5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range
6 Chapter 6: Algorithms: Searching, Sorting, and Recursion
6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions
7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra
8 Chapter 8: Programming: Selection, Iteration, and Writing Code
8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code
9 Chapter 9: Programming: Procedures, Arrays, and Data Structures
9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)
10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality
10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback
11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs
11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs
12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design
12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding
13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption
13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs
14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection
14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing
15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments
15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored
16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity
16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs
6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency
Key Takeaways Explain This Topic AI
Selection sort always makes n(n − 1)/2 comparisons and at most n − 1 swaps; after pass k, the k smallest values are in their final positions.
Insertion sort makes only n − 1 comparisons on already-sorted data but n(n − 1)/2 on reverse-sorted data, so it is fast on nearly sorted lists.
After each bubble sort pass, the largest remaining value has moved to the end of the unsorted part; a swap flag lets the algorithm stop early when a pass makes no swaps.
Merge sort runs in O(n log n) in every case and is stable but needs O(n) extra memory; quicksort averages O(n log n) but degrades to O(n²) when pivots split the data badly.
A stable sort keeps records with equal keys in their original relative order, which matters when you sort by one field after another.
Last updated: September 2026
What this competency asks
ETS asks you to understand searching and sorting algorithms and to analyze sorting algorithms for correctness . The discussion questions ask you to describe common comparison-based sorts, such as insertion sort and selection sort, and to analyze the number of comparisons . ETS's sample question on this topic shows an unfamiliar sorting procedure and asks for the array after six iterations of its loop. The core skill is careful tracing, not memorized names.
Selection sort
On each pass, find the smallest value in the unsorted part and swap it into the first unsorted position. void selectionSort ( int[ ] a, int n )
- for ( int i ← 0; i < n - 1; i ← i + 1 )
- int minIndex ← i
- for ( int j ← i + 1; j < n; j ← j + 1 )
- if ( a[j] < a[minIndex] )
- minIndex ← j
- end if
- end for
- swap ( a, i, minIndex ) // exchanges a[i] and a[minIndex]
- end for
- end selectionSort
Trace on {29, 10, 14, 37, 13} :
- After pass Smallest found Array
- 1 (i = 0) 10 at index 1 { 10 , 29, 14, 37, 13}
- 2 (i = 1) 13 at index 4 {10, 13 , 14, 37, 29}
- 3 (i = 2) 14 at index 2 (no change) {10, 13, 14 , 37, 29}
- 4 (i = 3) 29 at index 4 {10, 13, 14, 29 , 37}
Comparisons: 4 + 3 + 2 + 1 = 10 = n(n − 1)/2 for n = 5. Selection sort always makes this many comparisons, even on sorted data. It does at most n − 1 swaps , which is useful when writing to memory is expensive.
Insertion sort
Keep a sorted prefix. Take the next value (the "key"), shift larger values in the prefix one place right, and insert the key into the gap. void insertionSort ( int[ ] a, int n )
- for ( int i ← 1; i < n; i ← i + 1 )
- int key ← a[i]
- int j ← i - 1
- while ( ( j ≥ 0 ) and ( a[j] > key ) )
- a[j + 1] ← a[j]
- j ← j - 1
- end while
- a[j + 1] ← key
- end for
- end insertionSort
Trace on {5, 2, 4, 6, 1} :
- i key Comparisons made ( a[j] > key ) Array after insertion
- 1 2 5 > 2 {2, 5, 4, 6, 1}
- 2 4 5 > 4, 2 > 4 (false) {2, 4, 5, 6, 1}
- 3 6 5 > 6 (false) {2, 4, 5, 6, 1}
- 4 1 6 > 1, 5 > 1, 4 > 1, 2 > 1 {1, 2, 4, 5, 6}
That is 1 + 2 + 1 + 4 = 8 value comparisons. On an already-sorted array, each key needs one comparison: n − 1 total, O(n) . On a reverse-sorted array, it needs n(n − 1)/2. Insertion sort is the best simple choice for nearly sorted data.
The condition ( j ≥ 0 ) and ( a[j] > key ) relies on checking j ≥ 0 first , so the array is never indexed at −1. This is short-circuit evaluation (Section 7.4).
Bubble sort
Compare adjacent pairs and swap any that are out of order. Each pass carries the largest remaining value to the end.
One pass on {5, 1, 4, 2, 8} : swap 5 and 1 → {1, 5, 4, 2, 8}; swap 5 and 4 → {1, 4, 5, 2, 8}; swap 5 and 2 → {1, 4, 2, 5, 8}; 5 and 8 stay. After pass 1: {1, 4, 2, 5, 8} , and 8 is in its final place.
With a swapped flag, bubble sort stops after a pass with no swaps. That gives n − 1 comparisons, O(n), on sorted data. Its worst case is n(n − 1)/2 comparisons and as many swaps, O(n²).
Divide-and-conquer sorts
Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves in linear time. The array can be halved about log₂ n times, and each level of merging does O(n) work, so the total is O(n log n) in every case . It is stable (when merging equal values, it takes from the left half first), but it needs O(n) extra memory for merging.
Quicksort picks a pivot , partitions the array so smaller values come before the pivot and larger ones after, and then recursively sorts each side. Its average is O(n log n) and it sorts in place, apart from its recursion stack. If the pivot is always the smallest or largest value (for example, taking the first element as the pivot on data that is already sorted), each partition removes only one element and the time degrades to O(n²) . A random pivot or a median-of-three choice makes that unlikely. Standard quicksort is not stable .
Stability
A sort is stable if records with equal keys keep their original relative order. Suppose a class list is already alphabetical and you sort it by grade level. A stable sort keeps each grade's students alphabetical. An unstable sort may not.
Summary table
Algorithm Best Average Worst Extra space Stable?
- Selection sort O(n²) O(n²) O(n²) O(1) No (standard version)
- Insertion sort O(n) O(n²) O(n²) O(1) Yes
- Bubble sort (with flag) O(n) O(n²) O(n²) O(1) Yes
- Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
- Quicksort O(n log n) O(n log n) O(n²) O(log n) average (recursion) No
- Analyzing an unfamiliar sort for correctness
When a question shows a sorting procedure you have never seen:
Trace a small input exactly as written, keeping a table of the array and the index variables after each loop iteration.
Check the loop bounds. An inner loop that stops one element early leaves the last element unsorted. Using ≤ n indexes past the end.
Check the comparison direction. < versus > decides ascending versus descending order.
Test edge cases: an empty array, one element, duplicates, and already-sorted and reverse-sorted input.
Count what the question asks for: passes, iterations of a specific loop, comparisons, or swaps. These are different quantities.