Skip to content

Instantly share code, notes, and snippets.

@Tomic-Riedel
Created February 20, 2022 06:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save Tomic-Riedel/911c59c43e6082502e6b821f5cf8c904 to your computer and use it in GitHub Desktop.
Save Tomic-Riedel/911c59c43e6082502e6b821f5cf8c904 to your computer and use it in GitHub Desktop.
An implementation of MergeSort in Dart
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