<<<<<<< HEAD

advance-sorting-algorithms-in-Python

Implement three advanced sorting algorithms—mergesort, quicksort, and heapsort—and investigate their performance on arrays of sizes n = 10^3, 10^5, 10^7, and 10^8

Advanced Sorting Algorithms Performance Analysis

This report presents an Implement three advanced sorting algorithms—mergesort, quicksort, and heapsort . Their performance is evaluated based on execution time, number of comparisons, and number of swaps/moves on datasets of varying sizes( n = 103, 105, 107, and 108) (108 was used instead of 109 due to hardware limitations.) The values in the arrays ranged from 1 to n, and each array was saved to a text file before the sorting process, as required by the question. Algorithm Descriptions:

1. Merge Sort

• Mechanism: It is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts them, and merges the sorted halves back.
• Time Complexity: O(nlogn) for all cases (best, average, worst).
• Space Complexity: O(n), as it requires additional space to accommodate the temporary sub-arrays during merging.
• Advantages: Stable, consistent performance.
• Disadvantages: Additional memory consumption.

2. Quick Sort

• Mechanism: A divide-and-conquer algorithm that selects a random pivot and divides the array in a manner that elements less than the pivot are placed before it, and elements greater are placed after it. It then sorts the partitions recursively.
• Time Complexity: O(nlogn) on average, but O(n2) in the worst case (i.e., when the smallest or largest element is always chosen as the pivot).
• Space Complexity: O(logn), due to the recursive call stack.
• Advantages: Fast on average, in-place, good cache performance.
• Disadvantages: Worst-case performance without good pivot selection.

3. Heap Sort

• Mechanism: A comparison-based in-place algorithm which first builds a max-heap from the input data. It then repeatedly extracts the maximum element from the heap and places it at the end of the sorted portion of the array.
• Time Complexity: O(nlogn) in all cases. It has deterministic performance growth.
• Space Complexity: O(1), as it is an in-place sort.
• Advantages: Predictable performance.
• Disadvantages: Not stable, often slower than QuickSort on small datasets. Performance Results: The following results were obtained by running each algorithm on the same dataset, with accurate counting of operations. Output:

Performance Comparison Table: Size (n) Algorithm Time (s) Comparisons Moves Swaps 1000 Merge Sort 0.0016s 8717 10976 0 1000 Quick Sort 0.0013s 10545 14470 7235 1000 Heap Sort 0.0021s 16849 18080 9040 100000 Merge Sort 0.2535s 1535894 1768928 0 100000 Quick Sort 0.2278s 2056143 2192512 1096256 100000 Heap Sort 0.5773s 3019324 3149704 1574852 10000000 Merge Sort 103.1019s 220101056 243222784 0 10000000 Quick Sort 121.4365s 293035568 321097548 160548774 10000000 Heap Sort 252.6762s 434636394 447670840 223835420 100000000 Merge Sort 1623.8615s 2532928749 2765782272 0 100000000 Quick Sort 1603.0416s 3299713051 3611106036 1805553018 100000000 Heap Sort 1982.1677s 5012885478 5143143034 2571571517 Note on Terminology: • For Merge Sort, Moves refers to the number of elements copied during the merge process (not swaps). • For Quick Sort and Heap Sort, Swaps refer to actual element exchanges. Moves = total data movements (2 per swap). • Comparisons are counted every time two elements are compared. Performance Graph: X-axis: Matrix size (n) on a logarithmic scale. Y-axis: Execution time in seconds. Each algorithm has a different colored line.

The graph clearly shows: • All three algorithms follow O(nlogn) growth. • Merge Sort and Quick Sort have nearly identical performance for large n. • Heap Sort is always behind, especially with n=108 Here too, it takes ~20% longer than the other two Conclusions and Observations:

• Time Complexity Verification: All three algorithms exhibit O(nlogn) growth in running time, confirming their theoretical complexity. The log-linear trend is evident for all dataset sizes.

• Speed Comparison: For n=103=> Quick Sort is fastest (0.0013s), with Merge Sort (0.0016s) second. For n=105=> Quick Sort is still slightly ahead (0.2278s vs 0.2535s). For n=107=> Merge Sort is faster (103.1s vs 121.4s), indicating better scalability. For n=108=> Quick Sort is slightly ahead again (1603s vs 1624s), but they are extremely close. Why is Merge Sort faster than Quick Sort at n=107? Despite Quick Sort's lead in the average-case, real-world performance depends on: • Cache efficiency: Merge Sort accesses sequentially. • Recursion depth: Deep recursion in Quick Sort is costly. • Random pivot randomness: Avoids worst-case, but does not guarantee good partitioning.

• Small vs. Large Datasets: Small datasets (n=103): Differences are negligible (<1ms), system noise prevails. Large datasets (n≥105): Algorithmic differences are significant. Choice of algorithm directly impacts performance.

• Operation Counts: Comparisons: o Heap Sort > Quick Sort > Merge Sort o Heap Sort performs the most comparisons due to repeated heapification. Swaps/Moves: o Merge Sort performs the most moves (all elements are copied during merging). o Heap Sort has the maximum number of swaps due to frequent rebalancing. o Quick Sort has decent swaps but achieves an edge through good partitioning.

• Space Complexity Impact: Although not directly measured in terms of time, the space complexity matters. • Merge Sort: O(n) extra memory, stable sort, consistent performance • Heap Sort: In-place O(1), advantageous when memory is limited. • Quick Sort: O(log n) stack space, general-purpose, fast average case.

The choice of sorting algorithm depends on application requirements:

• Stable sorting required Merge Sort
• Fast average performance, limited memory Quick Sort (with random pivot)
• Guaranteed O(nlogn) , minimal memory Heap Sort
• Large datasets, predictable performance Merge Sort
• Real-time systems (avoid worst-case) Avoid basic Quick Sort; prefer Heap or Merge
• The choice depends on data size, memory constraints, stability needs, and performance guarantees.

Final Summary: Algorithm Time Complexity Space Complexity Stability Key Mechanism Merge Sort O(n log n) O(n) Yes Divide & merge using temp array Quick Sort O(n log n) O(log n) No Random pivot partitioning Heap Sort O(n log n) O(1) No Max-heap extraction

b5142ed (Advance Sorting Algorithms)