2 Replies - 3362 Views - Last Post: 01 September 2012 - 12:50 PM

#1 William_Wilson   User is offline

  • lost in compilation
  • member icon

Reputation: 207
  • View blog
  • Posts: 4,812
  • Joined: 23-December 05

Merge Sort

Posted 02 January 2008 - 09:50 AM

Description: Easily adaptable to be used for any other primitive, Object or Comparable Object.Sorts an integer array using Merge Sort
	/**
	 *Merge Sort function, which returns the sorted version of the
	 *supplied array.
	 *-Divide and conquer approach
	 *
	 *@param list	An array of integers to be sorted
	 */
	public int[] mergeSort(int[] list)
	{
		return mergeSort(list, 0, list.length-1);		//start recurssion
	}
	
	private int[] mergeSort(int[] list,int start, int end)
	{
		if(start >= end)
			return new int[]{};			//too many splits (return unsortable array)
		
		int mid = (start + end)/2;		//middle point
		
		mergeSort(list,start,mid);		//split up left  half
		mergeSort(list,mid+1,end);		//split up right half
		
		//start sorting
		int left_end    = mid;
		int right_start = mid + 1;
		
		while((start<=left_end)&&(right_start<=end))
		{
            if (list[start] >= list[right_start])		//left most element of Left side > left most element of Right side
            {
				int temp = list[right_start];
				
                for(int i=right_start-1;i>=start;i--)
                {
                    list[i+1] = list[i];				//shift elements
                }
                list[start] = temp;						//insert element where it belongs
                mid++; right_start++;					//advance counters
            }
            start++;									//advance in either case
        }	
		return list;
	}


Is This A Good Question/Topic? 1
  • +

Replies To: Merge Sort

#2 William_Wilson   User is offline

  • lost in compilation
  • member icon

Reputation: 207
  • View blog
  • Posts: 4,812
  • Joined: 23-December 05

Re: Merge Sort

Posted 02 January 2008 - 09:50 AM

Description: Easily adaptable to be used for any other primitive, Object or Comparable Object.Sorts an integer array using Merge Sort
	/**
	 *Merge Sort function, which returns the sorted version of the
	 *supplied array.
	 *-Divide and conquer approach
	 *
	 *@param list	An array of integers to be sorted
	 */
	public int[] mergeSort(int[] list)
	{
		return mergeSort(list, 0, list.length-1);		//start recurssion
	}
	
	private int[] mergeSort(int[] list,int start, int end)
	{
		if(start >= end)
			return new int[]{};			//too many splits (return unsortable array)
		
		int mid = (start + end)/2;		//middle point
		
		mergeSort(list,start,mid);		//split up left  half
		mergeSort(list,mid+1,end);		//split up right half
		
		//start sorting
		int left_end    = mid;
		int right_start = mid + 1;
		
		while((start<=left_end)&&(right_start<=end))
		{
            if (list[start] >= list[right_start])		//left most element of Left side > left most element of Right side
            {
				int temp = list[right_start];
				
                for(int i=right_start-1;i>=start;i--)
                {
                    list[i+1] = list[i];				//shift elements
                }
                list[start] = temp;						//insert element where it belongs
                left_end++; right_start++;					//advance counters
            }
            start++;									//advance in either case
        }	
		return list;
	}

Was This Post Helpful? 0
  • +
  • -

#3 RCharles   User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 27
  • Joined: 12-August 12

Re: Merge Sort

Posted 27 August 2012 - 10:47 PM

I have tried this but It only can sort 4 elements.
Was This Post Helpful? 0
  • +
  • -

#4 William_Wilson   User is offline

  • lost in compilation
  • member icon

Reputation: 207
  • View blog
  • Posts: 4,812
  • Joined: 23-December 05

Re: Merge Sort

Posted 01 September 2012 - 12:50 PM

Your message to me shows you have made changes to the mergeSort function which is causing your issue. As the function(s) are displayed here they are not limited to sorting 4 elements.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1