merge sort algo
// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
function merge(list, start, midpoint, end) {
const left = list.slice(start, midpoint);
const right = list.slice(midpoint, end);
for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
if (topLeft >= left.length) {
list[i] = right[topRight++];
} else if (topRight >= right.length) {
list[i] = left[topLeft++];
} else if (left[topLeft] < right[topRight]) {
list[i] = left[topLeft++];
} else {
list[i] = right[topRight++];
}
}
}
function mergesort(list, start = 0, end = undefined) {
if (end === undefined) {
end = list.length;
}
if (end - start > 1) {
const midpoint = ((end + start) / 2) >> 0;
mergesort(list, start, midpoint);
mergesort(list, midpoint, end);
merge(list, start, midpoint, end);
}
return list;
}
mergesort([4, 7, 2, 6, 4, 1, 8, 3]);
4.25
4
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+= 1
else:
arr[k] = R[j]
j+= 1
k+= 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+= 1
k+= 1
while j < len(R):
arr[k] = R[j]
j+= 1
k+= 1
# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end =" ")
print()
# driver code to test the above code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print ("Given array is", end ="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end ="\n")
printList(arr)
Thank you!
4
0
3.67
3
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
#include <stdio.h>
// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[5]; //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}
while(i <= q)
{
b[k++] = a[i++];
}
while(j <= r)
{
b[k++] = a[j++];
}
for(i=r; i >= p; i--)
{
a[i] = b[--k]; // copying back the sorted list to a[]
}
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[] = {32, 45, 67, 2, 7};
int len = sizeof(arr)/sizeof(arr[0]);
printf("Given array: \n");
printArray(arr, len);
// calling merge sort
mergeSort(arr, 0, len - 1);
printf("\nSorted array: \n");
printArray(arr, len);
return 0;
}
Thank you!
3
0
Are there any code examples left?
New code examples in category Other
-
Other 2023-03-27 22:50:10 how to select the whole line in vscode with keyboard shortcut
-
Other 2022-03-27 22:45:24 income of a web developer
-
Other 2022-03-27 22:35:01 \pyrcc_main.py: File does not exist 'resources.qrc'
-
Other 2022-03-27 22:30:45 rick roll embed code
-
Other 2022-03-27 22:20:08 Circuit_04_Potentiometer
-
Other 2022-03-27 22:20:05 iterative power
-
Other 2022-03-27 22:15:11 flutter run all
-
Other 2022-03-27 22:10:05 when is karlson release
-
Other 2022-03-27 22:10:02 wp .htaccess example
-
Other 2022-03-27 22:00:08 bash pause in file read line by line