Sorting In Swift
SiDarthVader
37K views
Open Source Your Knowledge, Become a Contributor
Technology knowledge has to be shared and made accessible for free. Join the movement.
What is Merge Sort?
Merge Sort is a sorting algorithm that divides the array into two parts, right down the middle. What about odd numbered arrays? [3,4,5,1,0,8,1]
The array would get split after the 4th element and create two sublists. This process would be repeated till there is one single element in a few (7 to be exact in this situation) different 'sorted' sublists. One by one, the elements are compared and merged into a sorted array.
[3,4,5,1,0,8,1]
[3,4,5,1] [0,8,1]
[3,4] [5,1] [0,8] [1]
[3][4][5][1][0][8][1]
[3,4][5,1][0,8][1]
[3,4][1,5][0,8][1]
[1,3,4,5] [0,1,8]
[0,1,1,3,4,5,8]
Best-Case Complexity: O(n log(n)) Worst-Case Complexity: O(n log(n))
func mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end func
func merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
return c
end func
Add the code to sort the array using the Merge Sort algorithm
1
2
3
4
5
6
struct mergeSort {
func mergeSort(_ array: [Int]) -> [Int] {
}
}
Enter to Rename, Shift+Enter to Preview
Stuck? Check the solution here
func merge(arr1: [Int], arr2: [Int]) -> [Int] {
var arr1Index = 0
var arr2Index = 0
var sortedSublist = [Int]()
while arr1Index < arr1.count && arr2Index < arr2.count {
if arr1[arr1Index] < arr2[arr2Index] {
sortedArray.append(arr1[arr1Index])
arr1Index += 1
} else if arr1[arr1Index] > arr2[arr2Index] {
sortedArray.append(arr2[arr2Index])
arr2Index += 1
} else {
sortedArray.append(arr1[arr1Index])
arr1Index += 1
sortedArray.append(arr2[arr2Index])
arr2Index += 1
}
}
while arr1Index < arr1.count {
sortedArray.append(arr1[arr1Index])
arr1Index += 1
}
while arr2Index < arr2.count {
sortedArray.append(arr2[arr2Index])
arr2Index += 1
}
return sortedArray
}
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array }
let cutIndex = array.count / 2
let arr1 = mergeSort(Array(array[0..<cutIndex]))
let arr2 = mergeSort(Array(array[cutIndex..<array.count]))
return merge(arr1: arr1, arr2: arr2)
}
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content