Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///////////////////////////////////////////////////////////////////////////////////////// CLASS
- public class MergeSort
- {
- private int[] toSort;
- public MergeSort(int[] toSort)
- {
- this.toSort = toSort;
- }
- public int[] Sort()
- {
- int[] sorted = new int[toSort.Length];
- int[] tmp = new int[toSort.Length];
- int firstIndex = 0;
- int lastIndex = toSort.Length - 1;
- new MergeSortInternal(toSort, firstIndex, lastIndex, sorted, tmp).Sort();
- return sorted;
- }
- }
- ///////////////////////////////////////////////////////////////////////////////////////// CLASS
- class MergeSortInternal
- {
- private int[] toSort;
- private int[] sorted;
- private int[] tmp;
- private int leftIndex, rightIndex;
- public MergeSortInternal(int[] toSort, int firstElementIndex, int lastElementIndex, int[] sorted, int[] tmp)
- {
- this.toSort = toSort;
- this.sorted = sorted;
- this.tmp = tmp;
- this.leftIndex = firstElementIndex;
- this.rightIndex = lastElementIndex;
- }
- public void Sort()
- {
- if(OnlyOneElement())
- SortOneElementList();
- else
- RecursivelySortBothHalfsOfTheArrayAndMerge();
- }
- private bool OnlyOneElement()
- {
- return leftIndex == rightIndex;
- }
- private void SortOneElementList()
- {
- sorted[leftIndex] = toSort[leftIndex];
- }
- private void RecursivelySortBothHalfsOfTheArrayAndMerge()
- {
- SplitSortArray splitArray = new SplitSortArray(toSort, leftIndex, rightIndex, sorted, tmp);
- splitArray.SortLeftPart();
- splitArray.SortRightPart();
- splitArray.MergeSortedArrays();
- }
- }
- ///////////////////////////////////////////////////////////////////////////////////////// CLASS
- public class SplitSortArray
- {
- int[] toSort;
- int[] splitArray;
- int[] sorted;
- int leftSideStart;
- int leftSideEnd;
- int rightSideStart;
- int rightSideEnd;
- int leftCursor;
- int rightCursor;
- public SplitSortArray(int[] toSort, int firstElementIndex, int lastElementIndex, int[] sorted, int[] tmp)
- {
- this.toSort = toSort;
- this.splitArray = tmp;
- this.sorted = sorted;
- this.leftSideStart = firstElementIndex;
- this.rightSideEnd = lastElementIndex;
- SplitInTheMiddle();
- }
- private void SplitInTheMiddle()
- {
- int middle = (leftSideStart + rightSideEnd) / 2;
- this.leftSideEnd = middle - 1;
- this.rightSideStart = middle;
- }
- public void SortLeftPart()
- {
- new MergeSortInternal(toSort, leftSideStart, leftSideEnd, splitArray, sorted).Sort();
- }
- public void SortRightPart()
- {
- new MergeSortInternal(toSort, rightSideStart, rightSideEnd, splitArray, sorted).Sort();
- }
- public int[] MergeSortedArrays()
- {
- leftCursor = leftSideStart;
- rightCursor = rightSideStart;
- for (int i = leftSideStart; i < rightSideEnd; i++)
- {
- if(IsLeftSideEmpty())
- sorted[i] = TakeElementFromRightSide();
- else if(IsRightSideEmpty())
- sorted[i] = TakeElementFromLeftSide();
- else if(IsLeftElementSmaller())
- sorted[i] = TakeElementFromLeftSide();
- else
- sorted[i] = TakeElementFromRightSide();
- }
- return sorted;
- }
- private bool IsRightSideEmpty()
- {
- return rightCursor > rideSideEnd;
- }
- private bool IsLeftSideEmpty()
- {
- return leftCursor > leftSideEnd;
- }
- private bool IsLeftElementSmaller()
- {
- return tmp[leftCursor] < tmp[rightCursor];
- }
- private int TakeElementFromLeftSide()
- {
- int result = tmp[leftCursor];
- leftCursor++;
- return result;
- }
- private int TakeElementFromRightSide()
- {
- int result = tmp[rightCursor];
- rightCursor++;
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement