Created
February 20, 2022 06:11
-
-
Save Tomic-Riedel/911c59c43e6082502e6b821f5cf8c904 to your computer and use it in GitHub Desktop.
An implementation of MergeSort in Dart
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
List<int> mergeSort(List<int> array) { | |
// Stop recursion if array contains only one element | |
if(array.length <= 1) { | |
return array; | |
} | |
// split in the middle of the array | |
int splitIndex = array.length ~/ 2; | |
// recursively call merge sort on left and right array | |
List<int> leftArray = mergeSort(array.sublist(0, splitIndex)); | |
List<int> rightArray = mergeSort(array.sublist(splitIndex)); | |
return merge(leftArray, rightArray); | |
} | |
List<int> merge(left_array, right_array) { | |
List<int> result = []; | |
int? i = 0; | |
int? j = 0; | |
// Search for the smallest eleent in left and right arrays | |
// array and insert it into result | |
// After the loop only one array has remaining elements | |
while(i! < left_array.length && j! < right_array.length) { | |
if(left_array[i] <= right_array[j]) { | |
result.add(left_array[i]); | |
i++; | |
} else { | |
result.add(right_array[j]); | |
j++; | |
} | |
} | |
// Insert remaining elements of left array into result | |
// as long as there are remaining elements | |
while(i! < left_array.length) { | |
result.add(left_array[i]); | |
i++; | |
} | |
// Insert remaining elements of right array into result | |
// as long as there are remaining elements | |
while(j! < right_array.length) { | |
result.add(right_array[j]); | |
j++; | |
} | |
return result; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment