Sponsored
Sponsored
Merge Sort is a classic divide-and-conquer sorting algorithm that works in O(nlog(n)) time complexity and requires extra space proportional to the length of the array. The core concept is to divide the array into two halves, recursively sort each half, and then merge the sorted halves to produce a sorted array.
Time Complexity: O(nlog(n))
Space Complexity: O(n) (for temporary arrays used during merging)
1
The C solution uses the merge sort algorithm, implementing both the merge and mergeSort functions. The array is recursively split into halves, sorted, and merged. Extra arrays L and R are used for the merge process, ensuring the correct elements are compared and copied back to the original array.
Quick Sort is an efficient, in-place sorting algorithm that works in average O(nlog(n)) time complexity. This approach involves selecting a 'pivot' element from the array and partitioning the remaining elements into two subarrays according to whether they are less than or greater than the pivot. The subarrays are then sorted recursively.
Time Complexity: O(n2) in the worst case, O(nlog(n)) on average.
Space Complexity: O(log(n)) for recursive stack space.
1def swap(arr, i, j):
2 arr[i], arr[j] = arr[j], arr[i]
3
4def partition(arr, low, high):
5 pivot = arr[low]
6 i = low - 1
7 j = high + 1
8 while True:
9 while True:
10 i += 1
11 if arr[i] >= pivot:
12 break
13 while True:
14 j -= 1
15 if arr[j] <= pivot:
16 break
17 if i >= j:
18 return j
19 swap(arr, i, j)
20
21def quick_sort(arr, low, high):
22 if low < high:
23 pi = partition(arr, low, high)
24 quick_sort(arr, low, pi)
25 quick_sort(arr, pi + 1, high)
26
27nums = [5, 2, 3, 1]
28quick_sort(nums, 0, len(nums) - 1)
29print(nums)Python's quick sort uses in-place operations to reorder array elements around a pivot, chosen as the current low index. This decreases memory usage while maintaining efficient sorting.