Efficient Sorts (Merge Sort, Quick Sort)
Efficient Sorting Algorithms
Let's step up from the basic sorts to the heavy hitters: Merge Sort and Quick Sort. These algorithms use a "Divide and Conquer" strategy to achieve a much better time complexity of O(N log N) on average, making them suitable for sorting large datasets.
1. Merge Sort
Merge Sort is a classic example of a Divide and Conquer algorithm. It divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.
-
The Core Idea: Divide the list in half, recursively sort each half, and then merge the two sorted halves back together.
-
Implementation:
function mergeSort(arr) { if (arr.length <= 1) { return arr; } const mid = Math.floor(arr.length / 2); const leftHalf = arr.slice(0, mid); const rightHalf = arr.slice(mid); const sortedLeft = mergeSort(leftHalf); const sortedRight = mergeSort(rightHalf); return merge(sortedLeft, sortedRight); } function merge(left, right) { let resultArray = [], leftIndex = 0, rightIndex = 0; while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { resultArray.push(left[leftIndex]); leftIndex++; } else { resultArray.push(right[rightIndex]); rightIndex++; } } return resultArray .concat(left.slice(leftIndex)) .concat(right.slice(rightIndex)); } -
Complexity:
- Time:
O(N log N)in all cases. - Space:
O(N), as it requires extra space for the merged arrays.
- Time:
2. Quick Sort
Quick Sort is another Divide and Conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
-
The Core Idea: Pick a pivot, partition the array around the pivot, and recursively sort the partitions.
-
Implementation (Lomuto partition scheme):
function quickSort(arr, low = 0, high = arr.length - 1) { if (low < high) { const pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); // Sort the left part quickSort(arr, pivotIndex + 1, high); // Sort the right part } return arr; } function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its final place return i + 1; } -
Complexity:
- Time:
O(N log N)on average, butO(N^2)in the worst case (e.g., for already sorted data with a poor pivot selection strategy). - Space:
O(log N)on average (due to the recursion stack), butO(N)in the worst case.
- Time:
Key Takeaway: Merge Sort and Quick Sort are highly efficient, general-purpose sorting algorithms. Merge Sort offers guaranteed
O(N log N)performance but requires extra space. Quick Sort is often faster in practice and sorts in-place, but its worst-case performance isO(N^2). The choice between them depends on the specific requirements of the problem.
التالي · الدرس 76 من 92
Non-Comparison Sorts (Radix, Counting - conceptual)
قراءة 3 دقيقة
أنهيت 75 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

