do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort)
{
    list_T	*l;
    listitem_T	*li;
    sortItem_T	*ptrs;
    sortinfo_T	*old_sortinfo;
    sortinfo_T	info;
    long	len;
    long	i;

    /* Pointer to current info struct used in compare function. Save and
     * restore the current one for nested calls. */
    old_sortinfo = sortinfo;
    sortinfo = &info;

    if (argvars[0].v_type != VAR_LIST)
	semsg(_(e_listarg), sort ? "sort()" : "uniq()");
    else
    {
	l = argvars[0].vval.v_list;
	if (l == NULL || tv_check_lock(l->lv_lock,
	     (char_u *)(sort ? N_("sort() argument") : N_("uniq() argument")),
									TRUE))
	    goto theend;
	rettv_list_set(rettv, l);

	len = list_len(l);
	if (len <= 1)
	    goto theend;	/* short list sorts pretty quickly */

	info.item_compare_ic = FALSE;
	info.item_compare_numeric = FALSE;
	info.item_compare_numbers = FALSE;
#ifdef FEAT_FLOAT
	info.item_compare_float = FALSE;
#endif
	info.item_compare_func = NULL;
	info.item_compare_partial = NULL;
	info.item_compare_selfdict = NULL;
	if (argvars[1].v_type != VAR_UNKNOWN)
	{
	    /* optional second argument: {func} */
	    if (argvars[1].v_type == VAR_FUNC)
		info.item_compare_func = argvars[1].vval.v_string;
	    else if (argvars[1].v_type == VAR_PARTIAL)
		info.item_compare_partial = argvars[1].vval.v_partial;
	    else
	    {
		int	    error = FALSE;

		i = (long)tv_get_number_chk(&argvars[1], &error);
		if (error)
		    goto theend;	/* type error; errmsg already given */
		if (i == 1)
		    info.item_compare_ic = TRUE;
		else if (argvars[1].v_type != VAR_NUMBER)
		    info.item_compare_func = tv_get_string(&argvars[1]);
		else if (i != 0)
		{
		    emsg(_(e_invarg));
		    goto theend;
		}
		if (info.item_compare_func != NULL)
		{
		    if (*info.item_compare_func == NUL)
		    {
			/* empty string means default sort */
			info.item_compare_func = NULL;
		    }
		    else if (STRCMP(info.item_compare_func, "n") == 0)
		    {
			info.item_compare_func = NULL;
			info.item_compare_numeric = TRUE;
		    }
		    else if (STRCMP(info.item_compare_func, "N") == 0)
		    {
			info.item_compare_func = NULL;
			info.item_compare_numbers = TRUE;
		    }
#ifdef FEAT_FLOAT
		    else if (STRCMP(info.item_compare_func, "f") == 0)
		    {
			info.item_compare_func = NULL;
			info.item_compare_float = TRUE;
		    }
#endif
		    else if (STRCMP(info.item_compare_func, "i") == 0)
		    {
			info.item_compare_func = NULL;
			info.item_compare_ic = TRUE;
		    }
		}
	    }

	    if (argvars[2].v_type != VAR_UNKNOWN)
	    {
		/* optional third argument: {dict} */
		if (argvars[2].v_type != VAR_DICT)
		{
		    emsg(_(e_dictreq));
		    goto theend;
		}
		info.item_compare_selfdict = argvars[2].vval.v_dict;
	    }
	}

	/* Make an array with each entry pointing to an item in the List. */
	ptrs = (sortItem_T *)alloc((int)(len * sizeof(sortItem_T)));
	if (ptrs == NULL)
	    goto theend;

	i = 0;
	if (sort)
	{
	    /* sort(): ptrs will be the list to sort */
	    for (li = l->lv_first; li != NULL; li = li->li_next)
	    {
		ptrs[i].item = li;
		ptrs[i].idx = i;
		++i;
	    }

	    info.item_compare_func_err = FALSE;
	    info.item_compare_keep_zero = FALSE;
	    /* test the compare function */
	    if ((info.item_compare_func != NULL
					 || info.item_compare_partial != NULL)
		    && item_compare2((void *)&ptrs[0], (void *)&ptrs[1])
							 == ITEM_COMPARE_FAIL)
		emsg(_("E702: Sort compare function failed"));
	    else
	    {
		/* Sort the array with item pointers. */
		qsort((void *)ptrs, (size_t)len, sizeof(sortItem_T),
		    info.item_compare_func == NULL
					  && info.item_compare_partial == NULL
					       ? item_compare : item_compare2);

		if (!info.item_compare_func_err)
		{
		    /* Clear the List and append the items in sorted order. */
		    l->lv_first = l->lv_last = l->lv_idx_item = NULL;
		    l->lv_len = 0;
		    for (i = 0; i < len; ++i)
			list_append(l, ptrs[i].item);
		}
	    }
	}
	else
	{
	    int	(*item_compare_func_ptr)(const void *, const void *);

	    /* f_uniq(): ptrs will be a stack of items to remove */
	    info.item_compare_func_err = FALSE;
	    info.item_compare_keep_zero = TRUE;
	    item_compare_func_ptr = info.item_compare_func != NULL
					  || info.item_compare_partial != NULL
					       ? item_compare2 : item_compare;

	    for (li = l->lv_first; li != NULL && li->li_next != NULL;
							     li = li->li_next)
	    {
		if (item_compare_func_ptr((void *)&li, (void *)&li->li_next)
									 == 0)
		    ptrs[i++].item = li;
		if (info.item_compare_func_err)
		{
		    emsg(_("E882: Uniq compare function failed"));
		    break;
		}
	    }

	    if (!info.item_compare_func_err)
	    {
		while (--i >= 0)
		{
		    li = ptrs[i].item->li_next;
		    ptrs[i].item->li_next = li->li_next;
		    if (li->li_next != NULL)
			li->li_next->li_prev = ptrs[i].item;
		    else
			l->lv_last = ptrs[i].item;
		    list_fix_watch(l, li);
		    listitem_free(li);
		    l->lv_len--;
		}
	    }
	}

	vim_free(ptrs);
    }
theend:
    sortinfo = old_sortinfo;
}