Sorting Algorithms Flashcards

Flashcards for reviewing sorting algorithms: Merge Sort and Quick Sort.

Divide and Conquer Paradigm

Decompose a problem into simpler sub-problems of the same type, solve recursively, and combine the solutions.

Merge Sort - Split Step

Split the input array into two equal halves.

Merge Sort - Solve Step

Recursively sort the two subarrays independently.

Merge Sort - Combine Step

Combine the two sorted subarrays by merging to get an overall sorted array.

Quick Sort - Partition Step

Partition the input array according to a pivot.

Quick Sort - Solve Step

Recursively sort the two subarrays independently.

Quick Sort - Combine Step

Combine the two sorted subarrays by simple merging to get an overall sorted array.

Merge Sort - Worst-case Time Complexity

O(n log n)

Quick Sort - Worst-case Time Complexity

O(n^2)

Partition (in Quick Sort)

Splits an array into two subarrays, one with elements smaller than the pivot and one with elements greater than the pivot.

Efficient sorting algorithms based on divide-and-conquer

Merge sort, quick sort