You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Merge sort and quick sort are efficient comparison-based sorting algorithms with average-case time complexity of O(n log n), making them vastly superior to the O(n²) simple sorts for large datasets. Both use the divide and conquer paradigm. At A-Level, you must understand how each algorithm works, be able to trace them, and compare their complexities and trade-offs.
Merge sort uses a divide and conquer strategy:
A list of one element is inherently sorted, so the "base case" of the recursion is a single-element list.
FUNCTION mergeSort(arr)
IF LENGTH(arr) <= 1 THEN
RETURN arr
END IF
mid = LENGTH(arr) DIV 2
left = mergeSort(arr[0..mid-1])
right = mergeSort(arr[mid..end])
RETURN merge(left, right)
END FUNCTION
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.