合并排序创建堆栈溢出

Question

我不明白为什么这种合并排序导致堆栈溢出。是因为我没有基础案例，如果是的话，我会如何去添加它？对于像我这样的初学者来说，合并排序是相当先进的:(所以我会很感激任何帮助或建议 此外，我一直无法理解数据存储在哪里，一旦你递归地分割数组我知道分裂原始数组会破坏它分解成单个的元素，但如果是这些单个元素存储??

Sub Main() 
    Dim Array() As Integer = {5, 4, 3, 1, 2, 6} 
    Dim right As Integer = Array.Length - 1 'find right index 
    Dim left As Integer = 0 'set left index 
    mergeSort(Array, left, right) 
End Sub 

Sub mergeSort(Array, left, right) 
    Dim middle As Integer 
    If left < right Then 
     middle = (left + right)/2 

     'recursively split both halves of the array 
     mergeSort(Array, left, middle) 
     mergeSort(Array, middle + 1, right) 

     'sort individual elements 
     mergeSortedArray(Array, left, middle, middle + 1, right) 
    End If 
End Sub 

Sub mergeSortedArray(ByRef Array, left, middle, rbeg, right) 
    Dim pt As Integer = 0 
    Dim TempArray(6) 

    While (left <= middle) And (rbeg <= right) 'sort every element 
     If Array(left) < Array(rbeg) Then 
      TempArray(pt) = Array(left) 
      left += 1 
     Else 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
     End If 
     pt += 1 
    End While 

    If left > middle Then 
     While rbeg <= right 'left sub array exhausted 
      TempArray(pt) = Array(rbeg) 
      rbeg += 1 
      pt += 1 
     End While 
    Else 
     While left <= middle 'right sub array exhausted 
      TempArray(pt) = Array(left) 
      left += 1 
      pt += 1 
     End While 
    End If 

    For Each element In TempArray 
     Console.WriteLine(element & " ") 
    Next 
End Sub 

Answer 1

很多问题与此代码在VB合并排序会看起来更像是这样：

Sub Main() 
    Dim Array() As Integer = {5, 33, 3, 10, 2} 'make the array 

    'Split Array: you need the leftmost index & rightmost index 
    Split(Array, 0, 4) 
    Console.ReadKey() 

End Sub 

Sub Split(Array, left, right) 
    If left < right Then 'if the array has elements.. 
     Dim middle As Integer = (left + right) \ 2 'find halfway point 

     Split(Array, left, middle) 'split left array 

     Split(Array, middle + 1, right) 'split right array 
     'recursion keeps on splitting the two arrays until we have a bunch of single elements 

     'now sort and merge 
     Merge(Array, left, middle, right) 
    End If 
End Sub 
Sub Merge(ByRef Array, left, middle, right) 

    Dim SizeA As Integer = middle - left + 1 
    Dim SizeB As Integer = right - middle 
    Dim LeftArray(SizeA) As Integer 'set size of left array. 
    Dim RightArray(SizeB) As Integer 'set size of right array 

    'Left & Right pointers to keep track of what elements in the array we are referring to 
    Dim LP As Integer 
    Dim RP As Integer 

    For LP = 0 To SizeA - 1 
     LeftArray(LP) = Array(left + LP) 'assign 0 index of original array to left hand array (5) 
    Next 

    For RP = 0 To SizeB - 1 
     RightArray(RP) = Array(middle + 1 + RP) 'assign 1 index of original array to right hand array (33) 
    Next 

    'reset pointers 
    LP = 0 
    RP = 0 
    Dim i = left 'set a pointer for the original array 

    'swap elements if need be: 
    While LP < SizeA And RP < SizeB 
     If LeftArray(LP) <= RightArray(RP) Then 'if element in left array is smaller that the one in the right 
      Array(i) = LeftArray(LP) 'assign the left value to the original array 
      LP += 1 ' increment the left array's pointer 
     Else 
      Array(i) = RightArray(RP) 'otherwise the original array gets the right element 
      RP += 1 'increment the right array's pointer 
     End If 
     i += 1 'now increment the counter for our new array 
    End While 

    'Hang on...what if there are still elements in the left array 
    While LP < SizeA 
     Array(i) = LeftArray(LP) 'assign these elements to the new array 
     LP += 1 'increment the left pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'Hang on...what if there are still elements in the right array 
    While RP < SizeB 
     Array(i) = RightArray(RP) 'assign these elements to the new array 
     RP += 1 'increment the right pointer 
     i += 1 'increment the new array's pointer 
    End While 

    'write out the new array 
    For Each element In Array 
     Console.Write(element & " ") 
    Next 
    Console.WriteLine("") 
    'start the second pass 
End Sub